프로그래머스 ‘소수 찾기’ 문제 풀이

문제 설명

프로그래머스의 ‘소수 찾기’ 문제를 풀어보았다. 문제는 다음과 같다.

1부터 숫자 n 사이에 있는 소수의 개수를 반환하는 함수를 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
n은 2이상 1000000이하의 자연수입니다.

처음엔 매우 쉬운 문제라고 생각했었다. 소수를 찾는 방법은 잘 알고 있었기 때문이다. 예를 들어 11이 소수이려면, 11을 2~10까지로 나누었을 때 나누어 떨어지지 않아야 한다. 그런데 웬걸, 이 방식은 효율성 테스트에서 낙제하고 말았다. 내가 작성한 코드는 비효율적인 탐색 방법이었고, 더 효율적인 방법이 있다는 뜻이었다.

“어떻게 하면 가장 효율적으로 소수를 찾을 수 있을까?”
이를 생각하느라 골치가 조금 아팠던 게 사실이다.

문제 풀이

이 문제를 해결하려면 정수론에 대한 지식이 약간 필요하다. 다음을 보자.

1. 자연수 n은 소수의 곱으로 이루어진다. (n >= 2)
정수론에 대한 가장 기본적인 정리이다. 1보다 큰 자연수는 언제나 소수의 곱으로 이루어진다. 6은 2 * 3, 10은 2 * 5로 이루어지는 식이다. 이 규칙으로부터 무엇을 알 수 있을까?

바로 어떤 수가 소수인지 알려면 그보다 작은 소수로만 나누면 된다는 것이다.
예컨대, 11이 소수인지 알기 위해서 2~10까지로 나누어 볼 필요가 없다. 11보다 작은 소수인 2, 3, 5, 7로만 나누어보면 된다. 이것이 더 효율적인 방법이다.

2. 자연수 n이 √n 이하의 수들로 나누어 떨어지지 않으면 n은 소수다. (n >= 2)
이것이 가능한 이유는, n의 약수들의 곱셈은 √n을 기준으로 대칭적으로 나열되기 때문이다.

예를 들어, 12를 기준으로 한다면
1 * 12 | 2 * 6 | 3 * 4 | √12 * √12 | 4 * 3 | 6 * 2 | 12 * 1 임을 알 수 있다. (√12 = 3.46…)

이때 12가 소수인지 알려면 2와 3만을 검사해보면 된다.
(1은 소수의 정의에 따라 제외되고, 4와 6은 볼 필요가 없다.
4로 나누어 떨어질 값이라면, 3으로 이미 나누어 떨어지기 때문이다. 6도 마찬가지다)

따라서 n이 소수인지 판별하려면 √n 이하의 수까지만 검사하면 된다.
검사할 데이터가 제곱근 개 이하로 감소하므로, 더 효율적인 방법이다.

결론적으로, 1번과 2번을 종합하면 다음과 같은 결론이 내려진다.
n이 소수인지 판별하려면 √n 이하의 소수들만 검사하면 된다.

이를 바탕으로 코드를 개선해 보았다.

작성한 코드

다시 문제를 살펴보면 다음과 같았다.

1부터 숫자 n 사이에 있는 소수의 개수를 반환하는 함수를 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
n은 2이상 1000000이하의 자연수입니다.

function solution(n) {
    let answer = 0;
    const prime = []; // 풀이 1
    for (let num = 2; num <= n; num++) { // 풀이 2
        prime.push(num); // 풀이 3
        for (let i = 0; prime[i] <= Math.sqrt(num); i++) { // 풀이 4
            if (num % prime[i] === 0) { // 풀이 5
                prime.pop();
                break;
            }
        }
    }
    answer = prime.length; // 풀이 6
    return answer;
}

코드 풀이

prime은 소수를 저장하는 배열이다.
소수가 될 수 있는 수들을 num이라고 한다. 1은 소수가 아니므로 num에서 제외한다.
num을 일단 소수라고 가정하고 prime 배열에 삽입한다.
prime에 있는 소수들 중에서, √num보다 작은 소수가 있다면 반복문을 수행한다.
num을 √num보다 작은 소수로 나누었을 때, 나누어 떨어진다면 num은 소수가 아니다.
num을 prime에서 제외한 뒤, 내부 반복문을 빠져나온다.
prime에는 1부터 n 사이에 있는 소수가 저장된다. 이 배열의 길이가 정답이다.

위와 같이 개선한 코드를 바탕으로, 코딩 테스트를 무사히 통과하였다.

프로그래머스 결과

마치며

코드의 정확성 뿐만 아니라 효율성을 고려해야 한다는 것을 다시 한 번 깨달았다. 그리고 그것을 위해서는, 수학에 대한 지식을 기본적으로 갖추는 것도 중요함을 알게 되었다. 앞으로 더 훌륭한 개발자가 되려면, 수학에 대한 공부도 꾸준히 병행해야겠다는 생각이 든다.

(제 글에서 틀린 것이 있다면 꼭 지적해 주세요. 감사히 배우겠습니다)