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