Prime number generator with remarkable speed

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.

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;
}

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 .

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 :)

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.

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

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

@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.

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';
	}
}

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).

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

@haw03013

Bullshit

@haw03013

Bullshit

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

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.

@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.

@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....

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?

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));

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);
}