[BOJ] 2960번 에라토스테네스의 체 - JAVA(자바)

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

이젠 자신있는 소수 문제 💪💪

 

에라토스테네스의 체는 소수를 빠르게 판별할 수 있는 알고리즘으로 원래의 에라토스테네스의 체는 소수의 배수만 지우는 구조로 구현되는데 이 문제는 소수까지 지우는 것으로 해결해야된다. 지워진 숫자는 continue 를 통해 넘어갈 수 있어 소수를 구하는데 있어 효율적인 방식이다.

import java.util.*;

class Main {

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        int k = s.nextInt(); // k 번째 지우는 수
        int count = 0; // 몇 번째로 지우는 지 count
        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                if (arr[j] == 0) continue; // 지웠으면 패스

                arr[j] = 0; // 지운다. 
                count++;

                if (count == k) {
                    System.out.println(j);
                    return;
                }
            }
        }
    }
}

---

💡 참고

[Algorithm] 에라토스테네스의 체