[소수 구하기]
시간복잡도 : O(nloglongn)
간략한 설명
2부터 자기자신을 제외한 배수를 지워나간다. 반복되면서 2,3,5,7 … 등의 자신만 나눠지는 소수만이 살아남게 된다.
static private void Eratos() {
prime = new boolean[MAX+1];
prime[0] = false;
prime[1] = false;
for(int i=2; i<=MAX; i++) {
prime[i] = true;
}
//true가 소수
for(int i=2; i<=MAX; i++) {
for(int j=i*2; j<=MAX; j+=i) {
//해당 배수는 다 false
if(prime[i]) {
prime[j] = false;
}
}
}
}