[Algorithm/Java] 백준 2960번 - 에라토스테네스의 체

---

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

---

🔍 문제 풀이

알게된 점

에라토스테네스의 체는 소수의 배수를 지워나가며 소수만 남기는 방법이다.

소수를 효율적으로 찾을 수 있다.

💻 코드

import java.io.*;
import java.util.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int cnt = 0;
        int[] arr = new int[n+1];

        // 2부터 n까지 정수 저장
        for(int i=2; i<=n; i++){
            arr[i] = i;
        }

        for(int i=2; i<=n; i++){
            // 지운 수 건너뛰기
            if(arr[i] == 0) continue;

            // i의 배수 지우기
            for(int j=i; j<=n; j+=i) {
                if(arr[j] != 0){
                    arr[j] = 0; // 숫자 지우기
                    cnt ++;

                    // k번쨰로 지운 수 출력
                    if(cnt == k){
                        System.out.println(j);
                        return;
                    }
                }
            }
        }
    }
}