Welcome, guest | Sign In | My Account | Store | Cart

The sieve of Eratosthenes implemented in C++. I noticed another recipe that could be improved upon, making it faster and a bit prettier.

C++, 83 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83``` ```#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; } ```
 Created by Mathijs Romans on Sat, 8 Oct 2011 (MIT)