[BOJ] 2960

[HyomK]

백준 12960 에라토스테네스의 체
[문제유형] 수학 - 소수
https://www.acmicpc.net/problem/12960

에라토스테네스의 체

임의의 자연수 n이 있으면 그 이하미만의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘

기본적인 수행 방식은

1. 찾을 범위까지 수를 나열한 다음, 소수가 아닌 1을 지웁니다.
2. 다음으로 큰 소수인 2를 남겨두고 2의 배수를 모두 지웁니다.
3. 다음으로 큰 소수인 3을 남겨두고 3의 배수를 모두 지웁니다.
   4, prime(n) 다음으로 큰 소수인 prime(n+1)을 남겨두고 prime(n+1)의 배수를 모두 지웁니다.
   5, 더 이상 지울 수 없을 때, 남아있는 수들이 소수입니다

2960

이 문제에서는 소수를 남기지 말고 함께 지워 M번째 지워지는 수를 구하는 것이 문제이다.
즉 소수이더라도 배열에서 지워질 수 있음을 유의해야한다

if(!checker[i] && isPrime(i)){
               //배수를 제거한다
                for(j in i ..N step i){
                    if(!checker[j]){
                        checker[j] = true
                        cnt ++
                    }
                    if(cnt == K){
                        println(j)
                        return
                    }
                }
            }
        }