에라토스테네스, 소수

필요한것 : 불린형 배열

bool isPrime[MAX+1];
fill(isPrime, isPrime + MAX+1, true);
isPrime[1] = false;
for (int i = 2; i <= MAX; i++) {
	if (!isPrime[i]) continue;
	for (int j = i * i; j <= MAX; j += i)
		isPrime[j] = false;
}

 

j = i*i부터 탐색하는 이유는 i의 배수 중 i*2는 2의 배수때 걸러졌고, i*3은 3의 배수 때 걸러졌고...

 

O(nloglogn)