public static boolean [ ] primeSieve ( final int n ) { final int halfN = ( n + 1 ) >> 1 ; final boolean sieve [ ] = new boolean [ n + 1 ] ; // Initialize every integer from 2 onwards to prime. for ( int i = 2 ; i <= n ; ++ i ) sieve [ i ] = true ; int prime = 2 ; // first prime number // Loop to create the sieve. while ( prime < halfN ) { // Mark as composites multiples of the prime. for ( int composite = prime << 1 ; composite <= n ; composite += prime ) sieve [ composite ] = false ; // Skip over composites to the next prime. while ( ( ++ prime < halfN ) && ( ! sieve [ prime ] ) ) { } } return sieve ; }
Compute the Sieve of Eratosthenes .