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