Algorithm - Sieve of Eratosthenes

What

소수(prime numbers)를 판별하는 알고리즘.

출처: wikipedia

int map[500000]; 
// n의 최대치만큼 설정
int solution(int n) ;
	for (int i = 2; i * i < n; i++) if(!map[i]) {
    	/* 여기서 소수 출력을 하면 안 된다. sqrt(n)까지만 진행하므로,
        반드시 현재 loop 끝난 이후 2~n 범위 새로 만들어서 해야함. */
    	for (int j = i * i; j < n; j += i)
        	map[j] = 1;
    
    // 개수를 세고 싶다면
    int count = 0;
    for (int i = 2; i < n; i++) if (!map[i]) count++;
    return count;
}