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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	10607	5410	4584	51.627%

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 입력

10 7

예제 출력

9

코드

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class bj2960 {

    public static int N, K;
    public static int num[];

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        System.setIn(new FileInputStream("/Users/projooni/sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = 1;
        for(int tc=1; tc<=T; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            num = new int[N+1];

            for(int i=0; i<N+1; i++) {
                num[i] = i;
            }
            num[0] = -1;
            num[1] = -1;

            int result = 0;
            int cnt = 0;
            int k = 2;
            while(k < N+1) {
                for(int i=k; i<N+1; i+=k) {
                    if(num[i] != -1) {
                        cnt++;
                        if(cnt == K) {
                            result = num[i];
                            break;
                        }
                        num[i] = -1;
                    }
                }
                if(cnt == K) {
                    break;
                }
                k++;
            }

            bw.flush();
            bw.write(result + "\n");
        }
        bw.close();

    }

}

풀이

1. 에라토스테네스의 체 를 구현한다. (에라토스테네스의 체)
2. 숫자를 지우는 과정마다 카운트를 해서 K번째 지우는 숫자를 출력한다.