[백준] 2960. 에라토스테네스의 체

문제 링크

[백준] 2960. 에라토스테네스의 체

풀이 과정

에라토스테네스의 체를 구현한 코드입니다.

boolean[] prime = new boolean[N + 1];
Arrays.fill(prime, true);
prime[1] = false;

먼저 N까지의 수의 소수 판별 여부를 담기 위한 prime 배열을 선언한 뒤, 모든 요소를 true로 초기화해줬습니다. 1은 소수가 아니므로 false를 저장합니다.

outer:
for (int i = 2; i <= N; i++) {
    if (prime[i]) {
        cnt++;

        if (cnt == K) {
            System.out.println(i);
            break outer;
        }

        for (int j = i * i; j <= N; j += i) {
            if (prime[j]) {
                prime[j] = false;
                cnt++;

                if (cnt == K) {
                    System.out.println(j);
                    break outer;
                }
            }
        }
    }
}

문제 조건의 P에 해당하는 수도 지워야 하므로, cnt를 증가시킵니다. 이후 P의 배수들을 모두 지워줘야 하므로, cnt를 증가시켜 줍니다.

cnt를 증가시킬 때마다 그 수가 K인지를 확인한 후, K번째 지운 수에 해당되면 출력하고 반복문을 탈출합니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int cnt = 0;
        boolean[] prime = new boolean[N + 1];
        Arrays.fill(prime, true);
        prime[1] = false;

        outer:
        for (int i = 2; i <= N; i++) {
            if (prime[i]) {
                cnt++;

                if (cnt == K) {
                    System.out.println(i);
                    break outer;
                }

                for (int j = i * i; j <= N; j += i) {
                    if (prime[j]) {
                        prime[j] = false;
                        cnt++;

                        if (cnt == K) {
                            System.out.println(j);
                            break outer;
                        }
                    }
                }
            }
        }
    }
}