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

Faster prime generator (C++ recipe) by Mathijs Romans
ActiveState Code (http://code.activestate.com/recipes/577899/)

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
Download
 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 <boost/dynamic_bitset.hpp>
#include <cmath>
#include <iostream>
#include <vector>

/**
 * 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<unsigned long> getPrimes( unsigned long limit )
{
  std::vector<unsigned long> 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<unsigned long>( 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<unsigned long> primes = getPrimes( limit );
  std::cout << "Trere are " << primes.size() << " primes below " << limit << "." << std::endl;
  return 0;
}
Tags: primes, prime_generator