알고리즘) 1부터 주어진 수 까지의 소수 개수 구하기(에라토스테네스 체)

조건

• 입력 값은 2이상 20만 이하
• 첫 줄에 소수의 개수를 출력

 

1차로 작성한 코드

import java.util.Scanner;

public class Main {
    private int solution(int num) {
        int answer = 0;
        for (int i = 2; i <= num; i++) {
            int cnt = 0;
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) cnt++;
            }

            if (cnt == 2) answer++;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        System.out.println(main.solution(num));
    }
}

 주어진 수 N에 대해 1 부터 N 까지의 수 중에서 소수인 수의 개수를 출력하는 문제이므로, 단순히 1과 자기자신으로만 나뉘어지는 지를 확인하면 된다고 생각했다.. 그러나 이 방법은 모든 수를 자신의 값 만큼 반복해야 하는 방식으로 불필요한 루프를 도는 횟수가 많다.

 

최종 코드

public class Main {
    private int solution(int num) {
        int result = 0;
        int[] arr = new int[num + 1];
        for (int i = 2; i <= num; i++) {
            if (arr[i] == 0) {
                for (int j = 1; j * i <= num; j++) {
                    arr[j * i] = 1;
                }
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        System.out.println(main.solution(num));
    }
}

 관련 강의를 들으면서 '에라토스테네스 체' 라는 알고리즘을 처음 접했다. 기본적인 접근 방식은 다음과 같다.

1. 정확한 표현인지는 모르겠다만, 해당 인덱스(값)이 소수인지 아닌지의 의 두 가지 값만 체크하기 위해 배열을 사용한다.
2. 예를 들어, 자연수 N의 값으로 10이 입력되었다고 치자. 1 ~ 10 간의 소수의 개수를 구해야 하는데, 사실상 소수가 아닌 1은 확인해볼 필요가 없다. 그럼 2부터 검증하면 되는데, 이를 검증하기 위해서 우선 길이가 N + 1 ( = 11)인 배열을 생성한다. 왜 그런지는 다음 단계에서 알 수 있을 것이다. 'int[] array = new int[N + 1]'과 같이 배열을 생성하면, 이 배열은 인덱스를 0부터 10까지를 가진다. 그리고 이 인덱스의 값들은 처음에 모두 '0'이다.
3. 2부터 소수인 수를 구하면 되기 때문에, 2부터 도는 루프(for문)을 생성한다. 인덱스 2의 값은 0이기 때문에(2가 특정 수의 배수가 아니기 때문에) 소수의 개수를 1 증가시킨다. 그리고, 2보다 크고 자연수 N( = 10) 보다 작은 인덱스들 중에서 2의 배수에 해당하는 인덱스들을 모두 더이상 체크하지 않아도 되는 인덱스로 변환한다. 이 것을 해당 인덱스들의 값을 1로 변환하는 작업을 통해 수행할 수 있다.
4. 이후로도 가장 바깥쪽의 루프는 계속 돌리되, 이제 그 인덱스의 값이 0인 경우에만 소수의 개수를 증가시키고, 해당 인덱스의 배수가 되는 인덱스들을 체크한다. (값이 1인 인덱스는 애초에 특정 수의 배수라는 의미이기 때문에, 검증 조차 하지 않는다.)

---

 이 문제를 처음에 가장 원초적인 방식으로 풀었을 때에는 Time Limit Exception이 발생했다... Time Limit이 1000ms였던 문제로, 나는 1900ms 이상 나왔는데, 최종적으로 통과된 코드에서는 181ms가 걸렸다. 이래서 개발자는 알고리즘 공부를 해야하는 것 같다. 이 문제 하나로도 1/10 가량의 시간을 줄일 수 있었으니 말이다.

 

아래는 인증샷!