Generating prime number from 0 to n

When Initially I looked into this problem, it looks very difficult and time taking problem. But after some searching I found one Aha! algorithm. Sieve of Eratosthenes, (Greek: κόσκινον Ἐρατοσθένους). Eratosthenes, an ancient Greek mathematician written beautiful algorithm for finding all prime numbers up to a specified integer.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
Initially, let p equal 2, the first prime number.
Starting from p, count up by p and cross out thus found numbers in the list (which will be 2p, 3p, 4p, etc.).
Find the first number not yet crossed out after p; let p now equal this number (which is the next prime).
Repeat steps 3 and 4 until p is greater than n.
All the numbers in the list which are not crossed out are prime.

Algorithm is taken from wikipedia article
Following is my implementation :

#include <iostream>
#include <vector>
#include <algorithm>
#include "Timer.h"
void prime_generator(int n, std::vector<int>& prime_list ) {
    Timer t("Prime number generation starts");
    std::vector<int> sequence(n + 1,1);
    for ( int index = 2; index <= n; ++index) {
        if( sequence[index] ) {
            for ( int i = 2 * index; i <= n ; i += index ) {
                if ( sequence[i] ) {
                    sequence[i] = 0;
                }
            }
        }
    }
    for ( int i = 2; i <= n; i++) {
        if ( sequence[i]){
            prime_list.push_back(i);
        }
    }
    t.stop();
}
int main( int argc, char **argv ) {
    std::vector<int> prime_list;
    prime_list.reserve(10000000);
    prime_generator( 10000000 , prime_list );
    for ( std::vector<int>::iterator itr = prime_list.begin(); itr != prime_list.end(); ++itr) {
        std::cout << *itr << std::endl;
    }
}

For Timer Class see my previous post.
Time taken to generate prime number from 0 to 10000000.

avinash@avinash-laptop:~/work/prime$ ./a.out 
  Prime number generation starts
  -------------------------------
  User CPU Time  : 0.46 s
  System CPU Time: 0.04 s
  Wait Time      : 0.01 s
  -------------------------------
  Elapsed Time   : 0.51 s
Advertisements

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