[백준] 2960번 에라토스테네스의 체

에라토스테네스의 체는 특정 제한된 범위 내의 소수(prime number)를 찾는  고대 수학 알고리즘이다. 

 

이 알고리즘의 동작 방식은 다음과 같다.

 

20까지의 수 중 소수를 찾는다고 하면,

1. 2를 소수에 적는다. (2는 가장 작은 소수이다.)

2. 20까지의 소수 중 2의 배수를 지운다.

3. 지워지지 않은 가장 작은 수를 찾아 소수에 적는다.

4. 20까지의 해당 수의 배수를 지운다.

5. 3~4를 20까지 반복한다.

 

2의 배수를 지웠을 때 (1~2단계)

3의 배수를 지웠을 때(3~4단계)

 

이런 식으로 5단계까지 완료하면 남는 수가 제한된 범위까지의 소수이다.

위의 과정이 체처럼 소수들을 거른다는 느낌이 들어서 이 알고리즘의 이름을 에라토스테네스의 체라고 정말 잘 지은 것 같다는 생각이 든다.

 

백준 2960번 에라토스테네스의 체는 이 알고리즘을 이용하여 푸는 문제이다. 단순히 에라토스테네스의 체 순서에 따라 지워지는 수를 구하면 되는 문제이다. 

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());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        boolean[] seive = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            seive[i] = true;
        }

        int step = 0;
        int result = -1;
        for (int i = 2; i <= n; i++) {
            if (result != -1) break;
            for (int j = 1; i * j <= n; j++) {
                if (seive[i * j] == false) {
                    continue;
                } else {
                    seive[i * j] = false;
                    step++;
                    if (step == k) {
                        result = i * j;
                        break;
                    }
                }
            }
        }
        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}