Sieve of Eratosthenes

Introduction

The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.

Source

PDL

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., not exceeding n :
      A[j] := false

Output: all i such that A[i] is true.

The implementation below was quickly put together to support a couple of my Euler c++ solutions. I include it here for completeness.

THERE HAS BEEN NO ATTEMPT TO OPTIMIZE THE CODE BELOW

See: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

#if ! defined SIEVE_ERATOS_INCLUDED
#define SIEVE_ERATOS_INCLUDED

#include <vector>
#include <cmath>

class CSieveOfEratosthenes
{
public:
  CSieveOfEratosthenes(int a_upper = 0) : m_upper(a_upper), m_primes(nullptr)
  {
    init();
  }

  virtual ~CSieveOfEratosthenes()
  {
    delete m_primes;
  }

  int get_nth(int a_pos)
  {
    int value = 0;
    int count = a_pos;
    size_t i = 0;
    for ( i = 0; i < m_primes->size() && a_pos ; i++) {
      // cout << "O: " << i << endl;
      if( true == (*m_primes)[i] ){
        // cout << "    **" << endl;
        value = i;
        a_pos--;
      }
    }

    if( a_pos == 0 ){
      return value;
    }else{
      return 0;
    }
  }

  uint64_t sum(int a_max)
  {
    uint64_t total = 0;
    size_t i;
    for( i = 0; i < a_max ; i++){
      if( true == (*m_primes)[i]){
        total += i;
      }
    }
    return total;
  }

  void dump(void);

protected:
  void init()
  {
    delete m_primes;

    if( m_upper <= 0 ){
      return;
    }

    int sqrtupper = (int)floor(sqrt(m_upper));

    m_primes = new std::vector<bool>(m_upper,true);

    (*m_primes)[0] = false;
    (*m_primes)[1] = false;

    for (size_t i = 2; i <= sqrtupper ; i++ ) {
      // cout << "O:" << i << endl;
      if( true == (*m_primes)[i]){
        for (size_t j = (i*i); j < m_upper; j += i ) {
          // cout << "    I:" << j << endl;
          (*m_primes)[j] = false;
        }
      }
    }
  }

private:
  int m_upper;
  std::vector<bool>*  m_primes;
};

#endif // SIEVE_ERATOS_INCLUDED

Sieve of Eratosthenes

Introduction

Source

PDL

Header

See Also