010.cpp

Go to the documentation of this file.

//application of the sieve of Eratosthenes

#include <iostream>
#include <iomanip>

const unsigned largeN = 2e6;    //find all primes from 1 to N.
int count = 0;                  //count the numbers of primes that have found already.
bool primes[largeN + 1];        //index 0 is not needed.

int
next (int i)                    //move to next prime number
{
  int k;
  for (k = i + 1; k <= largeN; k++)
    if (primes[k] == 1)         //is prime
      break;

  return k;                     //if at end, k=largeN+1
}

double sumP = 0;                //sum of all primes

int
main ()
{
  for (int k = 1; k <= largeN; k++)
    primes[k] = 1;              //assume all numbers are prime

  int index = 2;                //starts with 2.
  count++;                      //2 is prime
  do
    {

      sumP += index;            //sum up the prime numbers

      int x = index * 2;
      while (x <= largeN)
        {
          primes[x] = 0;        //exlude all multiples of "number"
          x += index;
        }

      index = next (index);     //move on to next prime number

      count++;
    }
  while (index < largeN + 1);   //stop at end
  count--;                      //the last one is not within largeN.

  std::cout << "Sum of primes from 1 to " << largeN << " is " << std::
    setprecision (20) << sumP << std::endl;
  return 0;
}