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

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

15965번: K번째 소수

 

---

 

문제 설명

입력으로 숫자 하나를 받는데, 이 숫자 번째의 소수를 출력하면 된다.

ex) 입력: 1 이면 1번째 소수를 출력한다 -> 출력: 2

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static boolean prime[] = new boolean[8000002];

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

		int n = Integer.parseInt(br.readLine());
		List<Long> list = new ArrayList<Long>();

		prime();

		for (long i = 2; i < 8000000; i++) {
			if (!prime[(int) i]) {
				list.add(i);
			}
		}

		System.out.println(list.get(n - 1));
	}

	static void prime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i]) {
				continue;
			}

			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}
}

 

코드 설명

소수 구하는 알고리즘은 에라토스테네스의 체를 이용하였다.

for문을 2부터 8백만까지 돌렸는데, 이 정도 돌려야지 50만 번째 소수가 출력이 된다.

그리고 소수 값들을 List에 넣었는데, 소수 값이 int형을 벗어날 수 있으므로 Long으로 자료형을 준다.

그리고 출력은 입력받은 수 -1 번째 소수를 출력시킨다.

처음에는 소수가 int형을 벗어난다는 것을 생각을 못하고 있어서 25점을 받았었다..