[JAVA] 백준 15965번 : K번째 소수

 

---

 

• 생각

해당 숫자가 몇번째의 소수인지 찾으면 되는 문제이다. 소수를 찾는 것은 에라스토테네스의 체를 이용해 찾으면 될 것 같고, 에라스토테네스의 체 내에서 소수가 발견되면 몇번째 소수인지 체크하면서 반복문을 돌면 될 것 같다.

 

• 코드

정답 코드 : 에라스토테네스의 체를 이용해서 구해주는데, 위의 K 범위만큼 배열을 만들어서 사용하면 100점이 뜨지않는다. 이유는 500000를 입력하면 500000번째 소수를 구하는 것이기 때문에 범위를 더 크게 주어야한다. 점점 늘리면서 채점해봤는데 10000001정도에 100점이 뜬다.

 

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

public class Main {
	static int K;
	static int[] prime;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(prime[K - 1]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		prime = new int[10000001];
		boolean[] check = new boolean[10000001];
		int index = 0;

		// 에라스토테네스의 체
		for (int i = 2; i <= 10000000; ++i) {
			if (!check[i]) {
				prime[index++] = i;
				for (int j = i + i; j <= 10000000; j += i) {
					check[j] = true;
				}
			}
		}
	}
}