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