#include #include #include #include /** * Generate all prime numbers up to a limit * @param limit test for primality up to this limit, not including the limit * @return the prime numbers */ std::vector getPrimes( unsigned long limit ) { std::vector primes; // special cases if ( limit <= 5 ) { if ( limit > 2 ) { primes.push_back( 2 ); if ( limit > 3 ) { primes.push_back( 3 ); } } return primes; } // multiples of 2 and 3 will not be used, just add them by hand primes.push_back( 2 ); primes.push_back( 3 ); // crossed out nonprimes boost::dynamic_bitset<> crossOut( limit ); // add primes to result and cross out nonprimes unsigned long crossOutLimit = static_cast( sqrt( limit ) ) + 1; unsigned long i = 5; for ( ; i < crossOutLimit; i += 6 ) { for ( unsigned long d = 0; d != 4; d += 2 ) { unsigned long num = i + d; if ( !crossOut.test( num ) ) { primes.push_back( num ); for ( unsigned long j = num * num; j < limit; j += num ) { crossOut.set( j ); } } } } // add extra primes to result for ( ; i < limit - 2; i += 6 ) { for ( unsigned long d = 0; d != 4; d += 2 ) { unsigned long num = i + d; if ( !crossOut.test( num ) ) { primes.push_back( num ); } } } // one may be missing if ( i < limit && !crossOut.test( i ) ) { primes.push_back( i ); } return primes; } int main() { unsigned long limit = 10000000; std::vector primes = getPrimes( limit ); std::cout << "Trere are " << primes.size() << " primes below " << limit << "." << std::endl; return 0; }