007.cpp

Go to the documentation of this file.

//application of the sieve of Eratosthenes

#include <iostream>
const unsigned largeN = 2e5;    //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
}

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
    {
      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++;

      if (count == 10001)       //requested prime
        {
          std::cout << "The "<<count<<"-th prime is " << index << std::endl;
          return 0;             //stop the program.
        }

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

  std::cout << std::
    endl << count << " primes have found from 1 to " << largeN<<
    std::endl;
  return 0;
}