[알고리즘] 백준 2960 - 에라토스테네스의 체

분류 : 수학

1. 문제

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

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

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

2. 입력

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

3. 풀이

1) 에라토스테네스의 체

소수를 판별하는 알고리즘이다.
소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

2) 풀이

문제에 적혀있는 알고리즘을 그대로 코드로 구현하면 된다.

4. 코드

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

public class reseto_2960 {
    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

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

        int[] arr = new int[N-1];

         //숫자 저장
        for(int i=0;i<arr.length;i++){
            arr[i] = i+2;
        }

        
        //배열에서 제일 큰 숫자(제일 뒤에 숫자)
        int max_arr = arr[N-2];

        for(int i=0;i<arr.length;i++){
            //지금 숫자의 배수를 몇번 할수 있는지
            int max = max_arr/arr[i];
            
            //현재 숫자 저장
            int tmp = arr[i];

            //이미 삭제된 숫자면 패스
            if(tmp == -1)
                continue;
            
            //현재 숫자의 배수 삭제
            for(int j=1;j<=max;j++){
                
                //아직 삭제 안됐으면
                if(arr[tmp*j-2]!=-1){
                    K--;
                    //횟수만큼 지웠음
                    if(K==0){
                        System.out.println(arr[tmp*j-2]);
                        return;
                    }
                    //지우기
                    else{
                        arr[tmp*j-2] = -1;
                    }
                }
            }
        }

    }
}