Sieve of Eratosthenes

#define N 1000006
bool NonPrime[N];

NonPrime[0]=NonPrime[1]=true;
for (int i=2; i*i<N; i++)
if (!NonPrime[i])
for (int j=i*i; j<N; j+=i)
NonPrime[j]=true;

// O(n logn) is proved