Use Sieve of Eratosthenes to find all primes smaller than n
bool isPrime [ n + 1 ] ; memset ( isPrime , 1 , sizeof ( isPrime ) ) ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( isPrime [ i ] ) { for ( int j = 2 * i ; j <= n ; j += i ) isPrime [ j ] = 0 ; } }