[백준 1929번] 소수 구하기 (에라토스테네스의 체) - Java

시간	제한메모리	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	144964	40637	28686	26.791%

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

예제 입력 1

3 16

 

예제 출력 1

3
5
7
11
13

 

 

 

 

---

고려해야 할 알고리즘

위 문제는 에라토스테네스의 체라는 이름의 알고리즘을 통해 구현하면 쉽게 정답을 맞출 수 있다. 에라토스테네스의 체는 대량의 소수를 빠르게 찾을 수 있는 방법으로 고대 그리스 수학자 에라토스테네스가 발견했다. 이 알고리즘은 소수가 1과 자신만을 약수로 갖는다는 성질을 이용한다. 즉, 특정 수가 1과 자기자신을 제외한 다른 수의 배수일 경우, 그 수는 소수가 아니라는 점에서 착안된 알고리즘이다. 에라토스테네스의 체 알고리즘은 다음과 같다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 배열에 담는다. (만약 2부터 N까지의 소수를 구하고자 한다면 2~N의 값을 담고 있는 배열을 만들면 된다.)
2. 숫자 2에서 시작해 배열을 한바퀴 돌며 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 숫자 3에서 시작해 배열을 한바퀴 돌며 자기 자신을 제외한 3의 배수를 모두 지운다.
4. 위 과정을 모든 배열 값에서 진행한다. 만약 해당 배열 값이 이미 지워진 경우 작업을 수행하지 않고 건너뛴다.
5. 배열을 모두 돌며 이 작업을 수행했다면, 지워지지 않은 값들을 출력한다. (지워지지 않은 값들은 모두 소수이다.)

 

 

예시

2부터 7까지의 모든 수 중 소수를 판별하고자 한다.

1. 2부터 7까지의 값을 담은 배열을 생성한다.
2. 2에서 시작해 자기 자신을 제외한 2의 배수를 모두 지운다. (4, 6 삭제)
3. 3에서 시작해 자기 자신을 제외한 3의 배수를 모두 지운다. (6 삭제)
4. 4는 위 과정에서 이미 지워졌으므로 건너 뛴다.
5. 5에서 시작해 자기 자신을 제외한 5의 배수를 모두 지운다. (없음)
6. 6은 위 과정에서 이미 지워졌으므로 건너 뛴다.
7. 7에서 시작해 자기 자신을 제외한 7의 배수를 모두 지운다. (없음)
8. 배열을 모두 돌았으므로, 지워지지 않은 값을 모두 출력한다. (2, 3, 7 출력)

 

 

 

에라토스테네스의 체를 구현한 자바 코드

public void eratosthenesSieve(int N) {
        
        // 2부터 N까지의 모든 값을 담기 위한 배열을 준비한다.
        int[] sieve = new int[N + 1];

        // 준비된 배열에 2부터 N까지의 값을 담는다. (코딩의 편의를 위해 index와 배열 값을 일치시킴)
        for (int i = 2; i < sieve.length; i++) {
            sieve[i] = i;
        }

        // 에라토스테네스의 체를 동작시켜 소수가 아닌 값들을 지운다 (소수가 아닌 값 -> 0)
        for (int i = 2; i < sieve.length; i++) {
            
            // 이미 지워진 값인 경우 건너뛴다
            if (sieve[i] == 0) continue;

            // 자기자신을 제외한 모든 배수를 지우는 코드
            for (int j = 2 * i; j < sieve.length; j += i) {
                sieve[j] = 0;
            }
        }

        // 에라토스테네스의 체로 걸러진 모든 소수를 출력한다.
        for (int value : sieve) {
            if (value > 1) {
                System.out.println(value);
            }
        }
    }

 

 

 

문제풀이

import java.util.Scanner;

public class EratosthenesSieve {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        int N = in.nextInt();
        eratosthenesSieve(M, N);

    }

    public static void eratosthenesSieve(int M, int N) {
        int[] sieve = new int[N + 1];

        for (int i = 2; i < N + 1; i++) {
            sieve[i] = i;
        }

        for (int i = 2; i < N + 1; i++) {
            if (sieve[i] == 0) {
                continue;
            }

            for (int j = 2 * i; j < N + 1; j += i) {
                sieve[j] = 0;
            }
        }

        for (int value : sieve) {
            if (value >= M) {
                System.out.println(value);
            }
        }
    }

}