[TIL 2023.02.20] 소수 구하기 (algorithm)

이제 항해도 끝났지만... 비루한 개발 실력과 이제 프로젝트로는 채울 수 없는 깃잔디를 위해서 1일 1알고리즘을 실천하기로 했다. 사실은 간편하게 백준허브 chrome extension을 사용하고 싶었지만... 왜인지 나만 안된다...

그래서 직접 VS code로 1일 1커밋을 실천하고 있는데, 가벼운 예제지만 안 써놓으면 100% 까먹을 내용이 생겨서 간만에 TIL을 작성하기로 했다.

❓자바스크립트에서 소수 (prime number) 판별법

프로그래머스에서 소수 만들기 라는 문제를 푸는데, 소수 판별법의 종류는 여러가지가 있다는 것을 알게되었다.
그 중 아래 방법이 가장 시간복잡도 측면에서 효율적이라고 하니 따로 적어두려고 한다.

function isPrime(el){
// 1. isPrime이라는 함수의 매개변수 element가 있다.
    for (let i = 2; i <= Math.sqrt(el); i++) {
    // 2. i를 2부터 element의 제곱근의 값까지 설정하여 반복문을 돌린다.
        if (el% i === 0) {
        // 3. 반복문을 돌리며 element를 i로 나눈다.
        // 3-1. element를 i로 나눴을 때 나머지가 0, 즉 한번이라도 나누어 떨어진다면,
            return false;
            // 4. 해당 element는 소수가 아니다.
        }
    }
    return true;
    // 5. 반복문이 끝날때까지 나누어 떨어진적이 없다면, 해당 element는 소수다.
}

• n의 제곱근 (√n) 값으로 나누어 떨어지면 √n의 배수라는 뜻이므로 소수가 아니게 된다.
• 예를 들어보자면 25의 제곱근은 √25(5)다.
• 이때 5까지만 반복문이 돌아가더라도 25는 5의 배수이므로 i가 5일 때 나누어 떨어지게 되고 소수가 아님을 판별할 수 있다.

function solution(nums) {
    var answer = 0;
    for (let i = 0; i < nums.length; i++) {
    // 1. nums 배열의 길이까지 i를 설정하고, 0부터 시작해서 반복문을 돌린다.
        for (let j = i + 1; j < nums.length; j++) {
        // 2. 이때 반복문을 동일한 방법으로 하나 더 돌리되, j에 i의 다음 인덱스가 할당될 수 있도록 한다.
            for (let k = j + 1; k < nums.length; k++) {
            // 3. nums 배열에서 총 3개의 값을 더해야하기 때문에 k를 이용해서 반복문을 하나 더 돌린다.
            // 3-1. 이때 k는 3번째 숫자여야 하기 때문에 j의 다음 인덱스가 k에 할당될 수 있도록 한다.
                if (isPrime(nums[i] + nums[j] + nums[k])) {
                // 4. 위에 선언한 isPrime 함수의 매개변수로 i, j, k 인덱스 값을 가진 숫자 3개를 더한 숫자를 넘긴다.
                    answer++;
                    // 4-1. 만약 isPrime의 값이 true일 때 answer의 값을 1씩 증가한다.
                }
            }
        }
    }
    
    return answer;
    // 5. nums 배열에 숫자 3개 조합으로 해당 배열에서 최대 몇개의 소수가 나오는지 판별한다.
}

크게 어려운 내용은 아니었지만, 소수를 판별하는 방법을 몰라서 초반에 약간 헤맸었다.
그래도 역시 구글엔 많은 자료가 있어서 내가 필요한 부분은 어렵지 않게 구할 수 있었다.

출처:

• 배짱이가 되고싶은 개미 개발자
• 나를 제외한 천재들