문제: https://www.acmicpc.net/problem/1929

설명

우리가 아는 소수를 구하는 방식(2부터 해당 수까지 나누어보는)을 사용하면 시간초과가 발생한다.

시간초과를 해결하기 위해 대표적인 소수(Prime)판별 알고리즘인 에라토스테넷의 체를 이용해 문제를 풀이한다.

다음 코드와 같이 우리가 아는 소수 판별 알고리즘의 시간 복잡도는 모든 수를 확인해야하므로 O(N)의 시간 복잡도를 갖는다.

bool isPrime(int n){
	for(int i = 2; i <= n; i++){
    	if(n % i == 0) return false;
    }
    return true;
}    

하지만 8이라는 숫자를 살펴보면, 8 = 2*4 = 2*2*2 이므로 모든 수를 살펴보는 것은 비효율적이다. 따라서 특정 숫자의 제곱근까지의 약수만 살펴도 된다.

에라토스테네스체 풀이 방법은 여러 소수를 한번에 판별할 때 유용한데, 풀이 방법은 다음과 같다.

1. 이차원 배열을 생성해 값을 초기화한다.
2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다.(자기 자신 제외)
3. 이미 주어진 수는 건너뛴다.
4. 2부터 시작하여 남아있는 숫자들을 출력한다.(1이 소수가 아니라는 것을 기억하라!)

코드

위의 풀이를 참고하여 코드로 옮기면 다음과 같다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class P1929 {
    static int N, M;
    static int n_numbers[];
    static int numbers[];

    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

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

        n_numbers = new int[N + 1];
        numbers = new int[M + 1];
		
        // 큰 수를 기준으로 소수를 찾았다.
        for (int i = 0; i <= M; i++) {
            numbers[i] = i;
        }
        
		// 2부터 시작하여, 만약 해당 지점이 0이면 -> 지웠으므로 continue를 하였다.
        for (int i = 2; i <= M; i++) {
            if (numbers[i] == 0) {
                continue;
            }
            // 해당 수의 배수들을 모두 지운다. 
            // 자기 자신을 지우지 않기 때문에, 2 * i가 되는 것이다.
            for (int j = 2 * i; j < M + 1; j += i) {
            	// j = 4, 6, 8, 10, 12 ...
                // j = 6, 9, 12, 15, 18, ...
                // j = 10, 15, 20, 25, 30, ...
                numbers[j] = 0;
            }
        }
		
        // 작은 수(N)부터 큰 수(M)까지 0이 아닌 것만 출럭한다.
        // 1은 소수가 아니므로 건너 뛴다.
        for (int i = N; i <= M; i++) {
            if (numbers[i] == 1) {
                continue;
            }
            if (numbers[i] != 0) {
                sb.append(numbers[i]);
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}