Initially all numbers are considered Primes .
memset ( sieve , true , sizeof ( sieve ) ) ; sieve [ 0 ] = sieve [ 1 ] = false ; for ( long long i = 2 ; i <= N ; i ++ ) { if ( sieve [ i ] ) { for ( long long j = i * i ; j <= N ; j += i ) { sieve [ j ] = false ; } } }