[프로그래머스 코딩테스트] 소수 찾기(Java)

  문제 설명

  1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

  소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

  (1은 소수가 아닙니다.)

 

  제한사항

• n은 2이상 1000000이하의 자연수입니다.

 

  입출력 예

n	result
10	4
5	3

class Solution {
    public int solution(int n) {
        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            arr[i] = 1;
        }
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if (arr[i] == 0) {
                continue;
            }
            int num = i * 2;
            while (num <= n) {
                 arr[num] = 0;
                 num += i;
            }
        }
        int answer = 0;
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 1) {
                answer++;
            }
        }
        return answer;
    }
}

  위 풀이는 '에라토스테네스의 체'를 이용했습니다. 이는 소수를 판별할 때 가장 빠른 방법입니다. 특히 이 알고리즘은 특정 범위 내의 소수를 구할 때 유용합니다. 단순히 특정 숫자가 소수인지 아닌지를 판별하고자 한다면, 다른 방법을 추천합니다.

  n + 1 크기의 배열을 생성합니다. for문이 n만큼 순회하면서 i는 2부터 arr[i]를 1로 초기화합니다. arr 배열은 0과 1로 채워진 배열이 될 것입니다. arr[i]가 소수라면 1을, 아니라면 0을 원소로 가질 것입니다. arr를 초기화 하는 수는 무엇이든 무방합니다. 소수와 소수가 아닌 수(합성수)를 구분할 수 있다면 괜찮습니다. boolean으로 true와 false로 구분해도 좋습니다. 하지만 보편적이고 단순한 방법은 0과 1로 구분하는 법인 듯합니다.

 

int arr[] = {?, ?, 1, 1, 0, 1, 0, 1….}; arr[2] = 1; arr[3] = 1; arr[4] = 0; arr[5] = 1; arr[6] = 0; arr[7] = 1;

 

  풀이 진행상 아직 0으로 바꿔주지는 않았지만, 결과적으로는 위와 같은 결과를 도출할 예정입니다. arr의 index 0번째와 1번째는 어떤 값이 들어가는지 모르겠어서 ?로 남겨두었습니다. 아직 값을 지정하지 않았으니 Null일 수도 있겠네요. 하지만 0과 1이 소수가 아니라는 사실은 모두가 알고, 이 알고리즘에서 중요한 부분이 아니니 넘어갑시다.

  이후 for문은 소수가 아닌 arr[i]를 0으로 바꿔주는 과정입니다. 조건식이 i <= (int)Math.sqrt(n)인 이유는 일정 수 이상 넘어가면 대다수는 앞에서 걸러졌기 때문입니다. sqrt(n)는 그 일정수의 범위를 지정해주는 것입니다. 예를 들어, n을 100으로 가정해보겠습니다. sqrt(n)은 10입니다. 10 이하의 소수는 '2, 3, 5, 7'입니다. 2의 배수, 3의 배수, 5의 배수, 7의 배수일 경우 소수가 아니게 되는 것입니다. 이 계산은 순차적으로 진행됩니다. 2의 배수를 거르고, 3의 배수, 5의 배수, 7의 배수를 걸러줍니다. 4의 배수를 거를 필요는 없습니다. 이미 2의 배수를 거를 때 걸러졌기 때문입니다. 마찬가지로 6의 배수를 걸러줄 필요도 없습니다. 이와 같은 계산이 반복됩니다. sqrt(n)인 10을 초과한 11 역시 걸러줄 필요가 없습니다. 소수인 11을 제외한, '22, 33, 44, 55….'는 이미 앞선 계산에서 걸러졌기 때문입니다.

 

출처: 위키백과, 에라토스테네스의 체

 

  위 사진은 배수가 걸러지는 과정을 보여줍니다. 이 코드에서는 사진과 달리, 중복되는 배수의 경우(이미 0으로 바뀐 경우) continue로 넘어가므로 겹쳐 세어지지는 않습니다.

  while문에서 각 수를 계산하고 배수일 경우, arr[i]를 0으로 바꿔줍니다. 이는 앞서 설명한 원리와 같습니다.

  이 문제에서 구해야 할 것은 소수의 개수이므로 for문을 통해 arr[i]가 1일 경우, answer가 1씩 증가합니다. 배열 원소를 전부 더해주어도 같은 결과를 얻을 수 있습니다. (소수는 1, 아닌 수는 0으로 할당했을 경우에만)

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {
                    count++;
                }
            }
            if (count == 2) {
                answer++;
            }
        }
        return answer;
    }
}

  시간초과로 탈락한 코드입니다. 이중 for문으로 바깥 for문은 n까지의 숫자를 순회하고, 안쪽 for문은 i의 약수의 개수를 구합니다. 만약 count 즉, 약수의 개수가 2일 경우 소수라는 뜻이므로 answer가 1씩 증가합니다. 틀린 코드라고는 볼 수 없습니다. 하지만 이렇게 풀면 n이 작은 수일 경우에는 괜찮지만 n이 커질수록 연산량이 많아지다보니 시간적, 효율적인 측면에서 모두 좋지 않습니다. 아래 사진은 극명한 시간차를 보여줍니다.

 

왼쪽은 에라토스테네스의 체 방식, 오른쪽은 이중 for문 풀이

+) for문 대신 스트림으로 각 원소의 합을 구했을 때