[Java][Baekjoon]1960_에라토스테네스의 체

문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다.

 

예제로 주어진 N=10, K=7 의 경우를 진행해보면 다음과 같다.

 

 

위의 과정과 동일하게 풀이도 문제에 주어진 알고리즘의 순서대로 진행하면 된다.

1. 2~N까지 모든 정수를 ArrayList에 넣어준다.
2. ArrayList에서 가장 작은 숫자를 num이라고 한다.
3. num * i <= N 이면 해당 값을 ArrayList에서 삭제하고, K값을 하나 감소한다.
   (K가 0이 되었을 때, 마지막으로 삭제 한 정수가 결과값)
4. num * i > N 이면 다시 2번 단계로 간다.

 

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

	public static int N, K, res;
	public static ArrayList<Integer> list = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken()); // 2~N까지의 정수가 주어짐
		K = Integer.parseInt(st.nextToken()); // K번째로 삭제
		for (int i = 2; i <= N; i++)
			list.add(i);

		func(2);
		System.out.println(res);
	}

	public static void func(int num) {
		
		if (K == 0)
			return;

		int i = 1;
		while (K > 0) {
			if (num * i > N) {
				func(list.get(0));
				return;
			}
			if (list.contains(num * i)) {
				res = (Integer) num * i;
				list.remove((Integer) res);
				K--;
			}
			i++;
		}
	}
}

 

---

www.acmicpc.net/problem/2960

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