Prime number generator with remarkable speed

BevoX 1 Tallied Votes 674 Views Share

This is my solution for generating prime numbers. With this code hopefully you can generate prime numbers with incredible speed. The generated numbers will be stored in a text file titled as "Primes.txt".

I have a dual core machine, but this program does not support dual core architecture, so it can only use one of the cores. Still the speed results are remarkable. On my 5600+ AMD, it is capable of generating 1 million prime numbers less than 8 seconds!

Compiled and tried under Vista, and Ubuntu 8.10. I use VisualStudio 2008 on Vista, and Code::Blocks 8.02 on Linux.

There is one drawback, the only even prime number 2 won't be displayed, ever.

Clinton Portis commented: freaky fast +6
//PrimeGen_v3 by BevoX 06/02/2009
//#include <new> //uncomment this, or try with new.h if you get compiler errors beacuse of ba.what()
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <fstream>

using namespace std;

class Primes
{
    public : Primes( const unsigned int & );
             ~Primes(){ delete []array; };

             void FindPrime();
             void WriteOut();

    private : unsigned int *array, _size, divisor, n, skip;
              const unsigned int end;
              ofstream out_file;
};

int main()
{
    unsigned int end_param;

    cout << "PrimeGen_v3 by BevoX" << endl << "Enter the last element: ";
    cin >> end_param;
	// don't try to feed it with negative numbers, it can't handle them

    if( end_param < 2 )
    {
        cout << "Invalid interval!" << endl;
        cin.ignore( 1,'\n' );
        cin.get();
        exit(1);
    }

    cout << " * WORKING.." << endl;

    Primes Alpha( end_param );
    Alpha.FindPrime();
    Alpha.WriteOut();

    cout << " * FINISHED" << endl << "The results can be found in the 'Primes.txt' file." << endl;

    cin.ignore( 1,'\n' );
    cin.get();
    return 0;
}
Primes::Primes( const unsigned int & _end_param ) : end( _end_param ) // constructor
{
    if( ( end % 2) == 0 ) _size = end / 2; // even numbers won't be initialized -> half size
	else _size = ( end / 2) + 1;

	try{ array = new unsigned int [ _size ]; } // allocates memory
    catch( bad_alloc &ba )
    {
        cout << "! ERROR : " << ba.what() << endl;
        cin.ignore( 1,'\n' );
        cin.get();
        exit(1);
    }

    n = 1;

    for( unsigned int i = 0; i < _size; i++ ) //occupies array, with odd numbers
    {
        array[i] = n;
        n += 2;
    }
}
void Primes::FindPrime()
{
    divisor = sqrt( (float)end ); // sets the greatest divisor(square root of the last element)
    skip = 2; // starts the checking from the third element

    for( n = 3; n <= divisor; n += 2 ) // loops through divisors
    {
        for( unsigned int i = skip; i < _size; i++ )
        {
            if( array[i] % n == 0 ) array[i] = 0;
			// replaces the element with 0, if the number could be divided by 'n' - the divisor
        }
        skip++; /*increases skip everytime, when the inner loop finished, skipping the
		previously checked elements*/
    }
}
void Primes::WriteOut()
{
    out_file.open( "Primes.txt" );

    if( out_file )
    {
        for( unsigned int  j = 0; j < _size; j++ )
        {
            if( array[j] != 0 ) out_file << array[j] << " ";
        }
        out_file.close();
    }
    else
    {
        cout << "! ERROR -- Unable to create FILE !!!" << endl;
        cin.ignore( 1, '\n' );
        cin.get();
        exit(2);
    }
}
haw03013 0 Newbie Poster

That time is pretty good. I'm a Java programmer wondering how fast others can find prime numbers and I've got some code that will find 100,000,000 primes (it won't go past what an int can hold) in 14 seconds on a Pentium 2.1Ghz dual core. It uses bitsets instead of actual integers so it is much more memory and processor efficient.

Clinton Portis 211 Practically a Posting Shark

just out of curiosity i am trying to measure the performance of my basic algorithm vs. your algorithm... but i am having a math problem; for some reason I cannot peform this division:

seconds = (end-start) / CLOCKS_PER_SEC;

i viewed the value of CLOCKS_PER_SEC as defined in the codeblocks IDE and it's (i guess an arbitrary value) of 1,000.

for example, if my computation takes 17 clock ticks to compute, i expect to calculate .017 seconds, but for some reason I always get 0 seconds.

an explaination of my error and suggestions for improvement would be appreciated.

#include<iostream>
#include<iomanip>
#include<ctime>

using namespace std;

int main()
{
    clock_t start = 0,
            end = 0;

    int max = 0,
        counter = 0;

    float seconds = 0.0;

    bool is_prime = true;

    cout << "Enter number of primes to calculate: ";
    cin >> max;

    int i=2;
    start = clock();
    do
    {
        is_prime = true;

        for(int j=2; j<=i/2 && is_prime; j++)
        {
            if(!(i%j))
            {
                is_prime = false;
            }
        }

        if(is_prime)
        {
            cout << '#' << counter+1 << ": " << i << endl;
            counter++;
        }

        i++;

    }while(counter < max);

    end = clock();

    seconds = (end-start) / CLOCKS_PER_SEC;

    cout << fixed << setprecision(6);

    cout << "\n\nTotal computation time: " << (end-start) << " cycles, or " << seconds << " seconds. ";

    return 0;
}
Narue 5,707 Bad Cop Team Colleague

You're using integer arithmetic, any precision will be lost before the result is assigned to your float variable. Convert one of the operands to a floating-point type and it should work: ((float)end - start) / CLOCKS_PER_SEC .

Clinton Portis commented: muy bueno +6
jonsca 1,059 Quantitative Phrenologist Team Colleague Featured Poster

Double check it, but I think it amounts to an integer division (clock_t is usually a long int and I think the constant is an integer value). Cast one or both to float.

EDIT: Edged out by the Code Goddess :)

Clinton Portis commented: muy bien +6
Clinton Portis 211 Practically a Posting Shark

thank ya'll very much. i was for some reason mistakenly under the impression that an implicit cast should take place from clock_t to float.

fyi: i let my program run for about 5 minutes and it was only at about 250,000 prime numbers calculated.

the longer it runs, the slower it gets.

Zjarek 2 Junior Poster in Training

Just to tease you, this is quick program (written in 10 minutes) to generate primes using linear sieve.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
void genPrimes(int n, vector<int>& result){
	vector<bool> temp(n+1,true);
	temp[0]=temp[1]=false;
	for(int p=2;p*p<=n;){
		int q=p;
		int x;
		while((x=p*q)<=n){
			while(x<=n){
				temp[x]=false;
				x=p*x;
			}
			while(!temp[++q]);
		}
		while(!temp[++p]);
	}
	for (int i=0; i<=n; i++){
		if (temp[i]) result.push_back(i);
	}
}
int main(){
	vector<int> result;
	genPrimes(1000000,result);
	for (int i=0; i<result.size(); i++){
		cout<<result[i]<<'\t';
		if (i%10==0) cout<<'\n';
	}
}

With g++ and -O2 with writing to file (./a.out >a.txt) it works in 0.1 s and without optimisation in 0.5 s. Tested on ASUS eee Pc 900.
//edit 100 000 000 is generated in 2.343 s, but resulting file is to big to write it via output redirecting. Tested using time ./a.out | grep asdf

Clinton Portis 211 Practically a Posting Shark

Just for fun I let my program run all night...

Total # of clock ticks needed to compute 1,000,000 primes: 50,103,965
Total # of seconds needed to compute 1,000,000 primes: 50,104 sec
Total program execution time: 50,108 sec

at around 400,000 primes there was noticible slowing and the prime numbers could be read easily as they moved up the screen

at around 700,000 primes the program was slow enough where you could easily destinguish all digits of the number counter as primes were being produced.

i probably burned some life out of my cpu as it was using between 47% and 50% CPU.

towards the end of my program, just to qualify as a prime number, each number had to be tested over 6 or 7 million times.

Now for a little interesting useless trivia...

The one-millionth prime number is: 15,485,863

so in your math studies if you have a fraction or a root that has 15,485,863 in it, you'll know it can't be simplified any further.

Q: can you guess what the prime number is just before 15,485,863

haw03013 0 Newbie Poster

@Zjarek:
I hope your program was to tease us. It's written so that the first argument passed into genPrimes is the highest number checked, not how many primes it will generate. The code is extremely slow. I set it to check all numbers up to as high as an int could go (2,147,483,647) and it still hadn't finished in half an hour (1,800,000 milliseconds). When you get some code that can find the first 105,097,565 PRIME numbers (the last one being 2,147,483,647) in 15,174 milliseconds then you'll have fast code because that's what mine will do. I was wondering if anyone out there had any fast code and I figured that some C++ programmer would have done it.

Zjarek 2 Junior Poster in Training

In posted code there is bug with overflow.
Here is an atkins sieve try.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstring>
bool inline getbit(int a, unsigned int* b){
	return b[a>>5]&(1<<(a&0x1F));
}
void inline flipbit(unsigned int a, unsigned int*b){
	 b[a>>5]^=(1<<(a&0x1f)); //may work
}
void inline setfalse(unsigned a, unsigned *b){
	b[a>>5]&=~(1<<(a&0x1f));
}

using namespace std;
void genPrimes( vector<int>& result){
	int n=((1<<15)-1)*((1<<15)-1);
	unsigned int * kwad=(unsigned int*)malloc(1<<19+4);
	kwad[0]=0;
	for (int i=1; i<=(1<<17); i++){
		kwad[i]=kwad[i-1]+(i<<1)-1;
	}
	
	unsigned int * temp=(unsigned int*)malloc(1<<27);
	memset ((void*)temp,1<<27,0);
	int d=0;
	unsigned xx,yy,z,j,p;
	for(unsigned  i=1;i<(1<<15);i++){
		if (i%1000==0)cout<<i<<endl;
		for (j=1; j<(1<<15);j++){
			xx=kwad[i];
			yy=kwad[j];
			z=(xx<<2)+yy;
			p=z%12;
			if ((p==1||p==5)&&z<n)flipbit(z,temp);
			z=z-xx;
			if ((z%12==7)&&z<n) flipbit(z,temp);
			if (i<=j) continue;
			z=z-(yy<<1);
			if (z<n&&(z%12==11)) flipbit(z,temp);
	} }
	for (int i=5; i<(1<<15); i++){
		if (!getbit(i,temp)) continue;
		z=yy=kwad[i];
		while(z<n){
			setfalse(z,temp);
			z+=yy;
		}
	}


	for (int i=0; i<n; i++){
		if (getbit(i,temp)) result.push_back(i);
	}
}
int main(){
	vector<int> result;
	genPrimes(result);
	cout<<result.size();
	for (int i=0; i<result.size(); i++){
		if (i<1000) cout<<i+3<<'\t'<<result[i]<<'\n';
	}
}
mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster

Just for fun, I cooked up a little algorithm of my own, without going as far as getting into bit operation-style algorithms. So, in a few minutes or so I got this algorithm which I think is fairly elegant and short:

void genPrimeNumbers(int n) {
  vector< pair<int,int> > accum;
  accum.reserve(n);
  accum.push_back(pair<int,int>(2,4)); 
  cout << endl << setw(20) << 2; cout.flush();
  
  for(int i = 3; accum.size() < n; ++i) {
    bool is_prime = true;
    for(vector< pair<int,int> >::iterator it = accum.begin(); it != accum.end(); ++it) {
      while( it->second < i )
        it->second += it->first;
      if( it->second == i ) {
        is_prime = false;
        break;
      };
    };
    if(is_prime) {
      cout << "\r" << setw(20) << i; cout.flush();
      accum.push_back(pair<int,int>(i,i+i));
    };
  };
};

It just prints out the values and I have checked that it works.
The performance is reasonable given the low level of sophistication of the algorithm:
gets the first 100,000 primes in 5.37 seconds
gets the first 1,000,000 primes in 545 seconds
That is on a 2.8 GHz processor (the program is single-threaded so it uses only one of my 8 processors) with 8M of L3 cache... and the rest of the specs is not so relevant.

EDIT: For the record, the performance is about 20 times worse with the -O0 flag instead of the -O3 flag (-O4 or -O5 made no further improvement).

Clinton Portis commented: fast algorithm. few lines of code. +6
vijayan121 1,152 Posting Virtuoso

A fast (very fast) implementation of the Sieve of Atkin: http://cr.yp.to/primegen.html

The less well known Sieve of Sundaram:

#include <vector>
#include <algorithm>
#include <iostream>

// sieve of sundaram (naive implementation)
std::vector<int> generate_primes( int N ) 
{
    const int M = N / 2 ;
    std::vector<bool> sieve( M, true ) ;
    for( int i = 1 ; i < M ; ++i )
    {
        const int L = (M-i) / ( 2*i + 1 ) ;
        for( int j = i ; j <= L ; ++j )
            sieve[ i + j + 2*i*j ] = false ;
    }

    std::vector<int> primes ;
    primes.push_back(2) ;
    for( int i = 1 ; i < M ; ++i ) 
        if( sieve[i] ) primes.push_back( i*2 + 1 ) ;
    return primes ;
}

int main()
{
    std::vector<int> primes = generate_primes(100) ;
    std::for_each( primes.begin(), primes.end(), 
                   [] ( int n ) { std::cout << n << ' ' ; } ) ; // C++1x
    std::cout << '\n' ;
}

And the exotic visual sieve: http://plus.maths.org/issue47/features/kirk/index.html

Clinton Portis commented: a fast algorithm with few lines of code +6
Otagomark -2 Newbie Poster

@haw03013

Bullshit

deceptikon 1,790 Code Sniper Team Colleague Featured Poster

@haw03013

Bullshit

What an insightful way to bump a year old thread. Can you elaborate any?

Otagomark -2 Newbie Poster

Read the post I relpied to, do the math. When I relpy with "Bullshit" you know exactly what i mean, when someone makes a claim like the one I relpied to , you take it on faith. perhaps you should be asking him to elaborate.

deceptikon commented: The onus is on you to make clear your objection and provide evidence that it's valid. -2
mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster

@Otagomark

haw03013's claim is that his Java program finds 105 million prime numbers in 15.1 seconds. That's not that wild of a claim. I just took vijayan121's Sieve of Sundaram implementation, optimized it a little, ran it, and timed it for 105 million. I got 29.7 seconds, so it's not that far off. According to the link vijayan121 gave, the Sieve of Atkin implementation claims 8 seconds for primes up to 1 billion (i.e., N = 1,000,000,000), with the Sieve of Sundaram implementation, I got just about 13 seconds for the same feat. haw03013's algorithm, whatever it is, is certainly astoundingly fast, but it is within reason.

BTW, here is the "optimized" implementation of the Sieve of Sundaram:

#include <vector>
#include <iostream>

// sieve of sundaram
void generate_primes( int N ) {
    std::vector<bool> sieve( N >>= 1, true ) ;
    for(int j = 1, ii = 3; j < N; j += ((ii += 2) ^ 1) << 1 )
        for(int k = j; k < N; k += ii )
            sieve[k] = false;

    std::cout << 2 << '\n';
    for( int i = 1 ; i < N; ++i ) 
        if( sieve[i] ) std::cout << ( (i << 1) | 1 ) << '\n';
}

int main() {
    generate_primes(1000000000) ;
    std::cout << std::endl ;
}

When timing it, you must remove the printing code, of course. On my PC, it will run just under 13 seconds without printing, and about 21 seconds with printing. With N = 2147483647 (max 32bit integer), it will take 29.7 seconds without printing and 47 seconds with printing.

Otagomark -2 Newbie Poster

@mike_2000_17
On my Pc that does not generate primes.
2,5,7,11,13,17,23,25,31,35,37,41,47,53,55,61,65,67,73,77,83,91,95,97....

Microno 0 Newbie Poster

Reading about the posted visual sieve method I've written the following code that calculates primes under k^2 where k is any number. The code is as such:

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

int main()
{
    int k = 20000;
    int l = k*k;
    vector<int> integers (l);
    for (int n = 1; n<=l; n++)
    {
        integers[n] = n;
    };
    for (int n = 2; n<=l/2; n++)
    {
        for (int j = 2; j<=l/2 and (j*n)<=l; j++)
        {
            if(integers[j*n]!=0)
            {
                integers[j*n] = 0;
            };
        };
    };
    ofstream Primes;
    Primes.open("Primes.txt");
    for (int n = 1; n<=l; n++)
    {
        if (integers[n]!=0)
        {
            Primes << integers[n] << "\n";
        };
    };
    Primes.close();
    return(0);
}

Unfortunately it uses approximately 2GB of memory once k=22000 and at that point it is incapable of running since the console only supports up till 2GB. So I wanted to try and split the process and calculate using a segmented method where instead of running through all k^2 possibilities within one cycle instead go through 2^(log(k)) cycles and k^2/(2^(log(k)) possibilities in each cycle. I attempted to do this with the following code but it seems to hang up after starting and I was wondering how that problem could be solved:

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <fstream>

using namespace std;

int main()
{
    int k = 100;
    int f = pow(2,log10(k));
    int l = k*k;
    ofstream Primes;
    Primes.open("Primes.txt");
    for (int u = 1; u<=f; u++)
    {
        vector<int> integers (l/f);
        for (int n = 1; n<=l/f; n++)
        {
            integers[n] = (u-1)*l/f+n;
        };
        for (int n = 2; n<=l/2; n++)
        {
            for (int j = 2; j<=l; j++)
            {
                for (int p = 1; p<=l; p++)
                {
                    if(integers[p]==(j*n) and (j*n)<=l)
                    {
                        integers[p] = 0;
                    };
                };
            };
        };
        for (int n = 1; n<=(l/f); n++)
        {
            if (integers[n]!=0)
            {
                Primes << integers[n] << "\n";
            };
        };
        cout << "t";
        integers.clear();
    };
    Primes.close();
    return(0);
}

I hope you guys don't consider this hijacking the thread but how could I improve the code I've written?

vijayan121 1,152 Posting Virtuoso

You are trying to access elements beyond the end of the vector (in at least two places).

And you probably need to take care of of narrowing conversions: int f = pow(2,log10(k));

Microno 0 Newbie Poster

I realised that so I corrected the issue and this is the final code just in case it interests anyone:

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int main()
{
    unsigned long long k = 400;
    unsigned int f = pow(2,log10(k));
    unsigned long long l = k*k;
    unsigned int m = l/f;
    unsigned long long integers[m];
    ofstream Primes;
    Primes.open("Primes.txt");
    for (unsigned long u = 1; u<=f; u++)
    {
        for (unsigned long long n = 1; n<=m; n++)
        {
            integers[n] = (u-1)*m+n;
        }
        for (unsigned long n = 2; n<=(u+1)*l/f; n++)
        {
            for (unsigned long j = 2; j<=(u+1)*l/f and (j*n)<=l; j++)
            {
                for (unsigned long p = 1; p<=m; p++)
                {
                    //cout << integers[p] << "\n";
                    if(integers[p]==j*n) integers[p]=0;
                }
            }
        }
        for (unsigned long n = 1; n<=m; n++)
        {
            unsigned int l = 0;
            if (integers[n]!=l)
            {
                Primes << integers[n] << "\n";
                //cout << integers[n] << "\n";
            }
        }
        cout << "Phase " << u << " Complete \n";
    }
    Primes.close();
    return(0);
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.