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

문제 설명

• 에라토스테네스의 체를 구현하는 문제입니다.

접근법

• 숫자 크기만큼의 배열을 만듭니다. 저는 인덱스 사용의 편리함을 위해 0번째 칸을 주고 한칸 더 크게 만들었습니다.
• 지워졌으면 아무것도 하지 않습니다.
• 안지워졌으면 해당 숫자와 해당 숫자의 배수를 모두 지웁니다.
• 배열의 크기만큼 반복합니다.

정답

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] num = new int[N+1];
		int cnt = 0;
				
		for (int i = 2; i < num.length; i++) {
			for (int j = i; j < num.length; j+=i) {
				if(num[j] !=0) continue;
				num[j] = i;
				cnt++;
				if(cnt == K) {
					System.out.println(j);
					break;
				}
			}
		}
	}
}