BOJ_2960 : 에라토스테네스의 체

👉 문제링크

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

---

---

🔸 문제 분석 🔸

• 2부터 n까지 수를 선택한다.
  • 선택한 수와 n까지의 배수들을 차례로 지운다.
  • 지우지 않은 수가 남아있다면 반복한다.
• k번째 지운 수를 출력한다.

🔸 코드 🔸

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 count = 0;

        boolean[] arr = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            if (!arr[i]) {
                int j = 0;
                while (i * ++j <= n) {
                    if (!arr[i * j]) {
                        arr[i * j] = true;
                        if (++count == k) {
                            System.out.println(i * j);
                            System.exit(0);
                        }
                    }
                }
            }
        }
    }
}

🔸 코드 해석 🔸

• 지운 수를 확인하기 위핸 boolean배열 arr를 n+1크기로 선언해 인덱스를 수로 활용한다.
• 2부터 n까지 배열 arr를 순회하며 계산한다.
  • 만약 arr[i]가 false라면 아직 지우지 않았으므로 배수를 모두 지워준다.
  • j는 i에 곱할 값으로, 1부터 i * j가 n이 넘지 않을 때 까지 1씩 더한다.
  • arr[i * j]가 아직 지우지 않은 수라면, 카운트하며 true값을 저장한다.
  • 카운트가 k가 되면 i * j를 출력하고, 프로그램을 종료한다.

 

---

🔸 end 🔸

• 소수계산을 빨리하기위해 사용하던 알고리즘이어서 쉽게 풀 수 있었다.