[BOJ/JAVA] 2960번: 에라토스테네스의 체

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

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

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

키워드

1. 2부터 N까지 모든 정수를 적는다.

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

---

구현

• 해당 문제대로 구현을 하면 된다.

solution

• N+1 크기의 boolean 배열을 생성한다.

• i=2부터 N까지 반복한다.
  • i를 지우고, i의 배수를 전부 지운다.

---

코드

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

public class java_2960 {
    static int N, K;
    static boolean numbers[];

    // K번째 지워진 수를 반환하는 메소드
    static int solution() {
        numbers = new boolean[N + 1];

        int count = 0;

        for (int i = 2; i <= N; i++) {
            if (numbers[i]) {
                continue;
            }

            // i의 배수를 모두 지운다.
            for (int j = i; j <= N; j += i) {
                if (numbers[j]) {
                    continue;
                }

                numbers[j] = true;
                count++;

                if (count == K) {
                    return j;
                }
            }
        }

        return -1;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int result = solution();

        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T