[백준] 2960 에라스토테네스의 체 (수학) - Java

2960번: 에라토스테네스의 체

2960번: 에라토스테네스의 체

문제설명

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

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

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

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

 

 

2부터 120 사이의 소수를 찾는 알고리즘 예시

1. 2부터 120까지 모든 정수를 적는다.
2. 가장 작은 수인 2는 소수이다.
3. 2를 지우고 2의 배수를 순서대로 지운다.
4. 지워지지 않은 수 중 가장 작은 수인 3은 소수이고, 3의 배수를 지운다.
5. 모든 수가 지워질 때까지 이 과정을 반복하여 소수를 찾아낸다.

 

접근법

2부터 N까지 정수를 채운 배열에서 for문을 이용해 배수를 지워나감

 

문제 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        int count = 0;

        int[] arr = new int[N+1];
        for(int i=2; i<=N; i++){    // 2부터 N까지 정수를 채움
            arr[i] = i;
        }

        for(int i=2; i<=N; i++){
            for (int j=i; j<=N; j+=i) {     // 배수 지우기
                if (arr[j] != 0) {
                    count++;
                    if (count == K) System.out.println(arr[j]);
                    arr[j] = 0;
                }
            }
        }
    }
}