[백준 / BOJ] 2960번 : 에라토스테네스의 체 JAVA

 

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

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

 

이 역시 [소수의 연속합]에서 사용했던 에라토스테네스의 체를 복습할 겸 풀어보았다. 문제 자체에서 에라스토스테네스의 체를 잘 설명해주고 있다.

 

위 문제를 풀었을 때에는 소수가 아닌 값을 구할 때 while문을 통해 곱해주었지만, 이번에는 for문을 사용해보았다. 다른 사람의 코드를 봤을 때 이 편이 조금 더 깔끔해보였기 때문이다.

그를 바탕으로 작성한 에라토스테네스의 체는 다음과 같다.

		for (int i = 2; i <= N; i++) {
			if(num[i]) continue;
			for (int j = i * 2; j <= N; j += i) {
				if(num[j]) continue;
				num[j] = true;
			}
		}

j를 처음부터 i의 2배수로 두고, 그 후에는 곱셈처럼 i를 계속 더해주는 게 포인트다.

 

하지만 이번 문제에서는 K번째로 지울 숫자를 구해야하고, 그에 더해 소수 또한 순서에 맞게 지워야 해서 조금 바꿔야 했다. 몇 번째로 지우는 것인지 count를 추가하고, i * 2부터 지우기 시작하는 것이 아니라, i 자체부터 시작했다.

		for (int i = 2; i <= N; i++) {
			if(num[i]) continue;
			for (int j = i; j <= N; j += i) {
				if(num[j]) continue;
				num[j] = true;
                cnt++;
			}
		}

 

결과적으로 제출한 코드는 다음과 같다.

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[] num = new boolean[N+1];
		int cnt = 0;
		int answer = 0;
		int sq = (int) Math.sqrt(N);
		for (int i = 2; i <= N; i++) {
			if(num[i]) continue;
			for (int j = i; j <= N; j += i) {
				if(num[j]) continue;
				num[j] = true;
				cnt++;
				if(cnt == K) answer = j;
			}
		}
		
		System.out.println(answer);
	}

}