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

https://www.acmicpc.net/problem/2960

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

 

 

 

 

 

예전에 소수 판별 알고리즘으로 유명한 에라토스테네스의 체 관련 문제를 푼 적이 있는데 그거랑은 다른 문제이다. 그건 시간 초과나고 어려웠는데, 이 문제는 그냥 에라토스테네스의 체의 원리를 적용해서 풀어보는 문제이다.

 

 

 

 

 

숫자 N에 대해 에라토스테네스의 체를 적용하여 소수가 아닌 수를 지워나갈 때, K번째로 지워지는 수를 찾는 문제이다.

 

각 수의 지워졌는지 여부를 파악할 boolean 배열을 만들었다.

 

1. K번째로 지워지는 수를 찾을 때까지 반복한다.

1. 아직 지우지 않은 수 중 가장 작은 수 P를 찾고, 지운다.

2. P의 배수를 찾아 지운다.

 

 

 

 

코드

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

public class Main {

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

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		boolean[] arr = new boolean[N + 1];
		
		int count = 0;
		int answer = 0;
		
		while(true) {
			//P 찾기
			int P = 0;
			for(int i = 2; i <= N; i++) {
				if(!arr[i]) {
					P = i;
					break;
				}
			}
			
			//P의 배수 지우기
			int i = 1;
			int n = P * i;
			
			while(n <= N) {
				if(!arr[n]) {
					arr[n] = true;
					count++;
				}
				
				if(count == K) {
					answer = n;
					break;
				}
				
				i++;
				n = P * i;
			}
		
			if(count == K) break;
		}
		
		System.out.println(answer);
	}

}

 

 

 

 

 

 

결과