[Baekjoon] 9842_Prime

문제(출처: https://www.acmicpc.net/problem/9842)

---

< Prime >

 

문제 풀이 

 

에라토스테네스의 체를 사용하여 n번째 소수를 구한다.

 

 my solution (Java)

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

public class _9842_ { // Prime

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

		int n = Integer.parseInt(bf.readLine());

		boolean arr[] = new boolean[100000001];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i <= Math.sqrt(100000001); i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 100000001; j += i) {
					arr[j] = true;
				}
			}
		}

		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 2; i < 100000001; i++) {
			if (!arr[i]) {
				list.add(i);
			}
		}

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

변수)
n : n번째
arr : 소수 판별
list : 소수만 저장한 list

 

n을 입력받는다. 에라토스테네스의 체를 사용하여 100000000까지 소수를 판별한다. 소수라면 ArrayList에 저장한다. 

 

최종 ArrayList의 n-1번째 값을 출력한다.

 

---

---