/ BOJ

BOJ_2960_에라토스테네스의체_JAVA

문제 : 에라토스테네스의 체

링크 : BOJ_2960_에라토스테네스의체

접근 방식

에라토스테네스의 체는 유명한 소수 구하는 방법이다.

2부터 시작하여 2의 배수, 3의 배수, 5의 배수… 와 같이 가장 작은 소수인 정수의 배수를 삭제하는 방식으로 소수를 구할 수 있다.

그 내용을 그대로 구현하면 된다.

boolean 배열을 N+1까지 생성한다.(기본값 false), 2부터 N까지 반복문을 돌리면서, 소수인 수의 배수들을 true처리 하고 카운팅을 한다. 카운팅이 K에 도달했을 때 지운 수를 출력하면 된다.

소스 코드

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

public class BOJ_2960_에라토스테네스의체 {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine());

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

		int K = Integer.parseInt(st.nextToken());
		boolean[] arr = new boolean[N + 1];
		int cnt = 0;
		while (true) {

			for (int i = 2; i <= N; i++) {
				if (!arr[i]) {
					int P = i;
					arr[i] = true;
					cnt++;
					if (cnt == K) {
						System.out.println(i);
						System.exit(0);
					}
					for (int j = P; j <= N; j += P) {
						if (!arr[j]) {
							arr[j] = true;
							cnt++;
							if (cnt == K) {
								System.out.println(j);
								System.exit(0);
							}

						}
					}
				}
			}
		}
	}

}

이 문제는 난이도가 더 내려가도 된다고 생각한다. 생각도 간단했고 구현도 쉬웠다.