Home > Programming, Technology > Sieve of Eratosthenes CPP source code

Sieve of Eratosthenes CPP source code


Seive of Eratosthenes is one of the mostly used prime generation algorithms.
Algorithm is very simple and straight forward.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).
5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.
When the algorithm terminates, all the numbers in the list that are not marked are prime.

Improvements over Seives of Eristhones:
One of the improvements that can reduce the larger computation is not including 2’s multiples (however, the only even and prime number is 2). Just considering only the odd numbers we can reduce prime holding array size and improve performance.

The following C++ uses the above improvement and considers each element of primes array as an odd number i.e. primes[n] represents 2*n+1 number in real. At the end of the operation primes array will have one’s in all the corresponding indices of prime numbers.

The below code can be seen running using ideone online compiler

// Written by Vasanth Raja Chittampally
// Source Code: Sieve of Eratosthenes
// All rights are reserved
#include #include
#include
void seive(int start, int range, int * primes)
{
//Seiving is done here
long start1 = clock();
for(int i = 6; i {

int iter = 2 * i + 1;
if(primes[i] == 1)
{
int startInLoop = start / iter;
if(startInLoop % 2 == 0)
startInLoop++;
if(startInLoop < 13)
startInLoop = 13;
for(int j = startInLoop * iter; j primes[(j - 1) / 2] = 0;
}
}
std::cout< int count = 0;
// display the results
for(int i = start / 2; i if(primes[i] != 0)
{
//std::cout<< 2 * i + 1 << " ";
count++;
}
std::cout< }
int main(void)
{
const int range = 5000000 ;

const int start = 1000000 ;
int * primes = new int[range / 2 + 1];
long time1 = clock();
for(int i = 0; i {
primes[i] = 1;
}
for(int i = 4; i {
primes[i] = 0;
}
for(int i = 7; i {
primes[i] = 0;
}
for(int i = 10; i {
primes[i] = 0;
}
for(int i = 16; i {
primes[i] = 0;
}
long totTime = clock() - time1;
std:: cout << std::endl< return 0;
}

The above code can be seen running using ideone online compiler

Advertisements
  1. July 8, 2014 at 11:59 pm

    Thanks on your marvelous posting! I definitely enjoyed reading it, you are
    a great author.I will ensure that I bookmark your blog and will come back from now on.
    I want to encourage you continue your great writing, have a nice holiday weekend!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: