백준 2960 에라토스테네스의 체(JAVA)

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

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

 

에라토스테네스의 체란 기본적인 알고리즘 개념을 알아야 풀 수 있는 문제입니다.

 

간단하게 설명하면 1부터 100까지 숫자가 있습니다.

1은 소수가 아니므로 제거하고, 2부터 100까지 소수인 2를 제외한 2의 배수들을 전부 제거합니다.

그 다음 3부터 100까지 제거, 5부터 100까지 ....

진행하다보면 0 2 3 0 5 0 7 0 0 0 11 0 13 .... 97 이런식으로 소수만 남는 구조가 나오는데

이러한 알고리즘이 에라토스테네스의 체입니다.

 

에라토스테네스의 체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

그리고 주의해야 할 점은 원래 에라토스테네스의 체 알고리즘은 배수를 제거하기 때문에 n * 2부터 진행하지만

이 문제는 n * 1부터 진행한다는 점을 잊지말고 풀어야 정답이 나옵니다.

 

import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.close();
 
        int arr[] = new int[1001];
 
        for (int i = 0; i <= 1000; i++) {
            arr[i] = i;
        }
 
        arr[0] = 0;
        arr[1] = 0;
 
        int ans = 0;
        int cnt = 0;
 
        era: for (int i = 2; i <= N; i++) {
            for (int j = 1; j * i <= N; j++) {
 
                if(arr[i*j]==0) continue;
                
                arr[i * j] = 0;
                cnt++;
 
                if (cnt == K) {
                    ans = i * j;
                    break era;
                }
                
            }
        }
        System.out.println(ans);
    }
}