1929번: 소수 구하기

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

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

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

---

[ 핵심 ]
1. 처음에 코드를 짜서 제출했을 때 시간초과가 발생하였다.
2. 소수를 구하는 여러 방법들 중 효율적인 것을 찾다가 에라토스테네스의 체 라는 것을 알게 되어 이것을 사용하였다.

에라토스테네스의 체
boolean 타입의 n+1개의 배열을 만든다. (소수는 false, 소수가 아니면 true 값을 가진다.) 0번 인덱스와 1번 인덱스는 소수가 아니므로 true 값으로 만든다. 2번 인덱스부터 부터 배열 길이의 제곱근까지 반복문을 돌리며 소수가 아니면 반복문을 계속 진행하고, 소수라면 해당 값의 제곱부터 배열의 길이까지 해당 값을 더하며 true(소수가 아니라고)로 만든다.

---

[ 풀이 ]

시간초과가 발생한 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        for(int i = M; i <= N; i++) {

            if(i == 1) continue;

            int count = 0;
            for(int j = 2; j <= i; j++) {
                if(i % j == 0) count++;
                if(count >= 2) break;
            }

            if(count == 1) sb.append(i).append("\n");

        }

        bw.write(sb.toString());
        bw.flush();
    }

}

에라토스테네스의 체를 이용한 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static boolean prime[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 입력받기
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 소수는 false, 소수가 아니면 true
        prime =  new boolean[N + 1];
        get_prime();

        for(int i = M; i <= N; i++) {
            if(!prime[i]) sb.append(i).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();

    }

    public static void get_prime() {

        prime[0] = prime[1] = true;

        for(int i = 2; i <= Math.sqrt(prime.length); i++) {

            // 소수가 아니면 계속 반복문 돌리기
            if(prime[i]) continue;

            // 소수이면 i의 배수들을 [ 소수가 아니라고 ] 표시
            for(int j = i*i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }

}