There are other simpler solutions... For example, the Sieve of Eratosthenes is good for numbers under 10 mil.

This piece of code calculates 1 mil. primes in 1.29 sec in a for loop.bool IsAPrime(int n) { for(int i(2); i<=sqrt(n); i++) if(n%i == 0) return true; return false; }

But this one does it under approximately 0.9 sec...int EratosthenesSieve (int upper, int array[]) { /* the function takes the upper limit to which we test the numbers in the arguments, as the array in which we store the numbers, but it returns the exact number of primes */ int size=0; int i; int sieve[18000]; // enough for 2000 primes.... memset(sieve,0,sizeof sieve); int tmp; for(int i(2); i<=upper; i++) { if(!sieve[i]) { array[size++] = i; tmp = i+i; while(tmp<=upper) { sieve[tmp] = 1; tmp+=i; } } } return size; }

Tested on Intel Dual Core 2.56 GHZ and 2GB RAM

There are better ways to do it, but these are the simplest...

Yes, there are a lot of different of ways of sieving for primes, but as it is in the title, it seems that the subject of this thread is the "Sieve of Eratosthenes", which is actually likely the best method up to a range of about 10 billion not 10 million as you state.

Your first example is both not complete and incredibly inefficient as to time performance since it is actually a Prime Sieve by Trial Division which is often mistakenly referred to as the Sieve of Eratosthenes, as per the OP's Wikipedia link which references this method: http://en.wikipedia....of_Eratosthenes. The trial division for all numbers less than the square root of the test number is as implied by the '%' modulo operation. Although Prime Sieve by Trial Division is very simple in terms of lines of code required, it is very computationally complex meaning that the CPU works very hard at computations and the number of those computations increase asymptotically with greater ranges. In fact, your logic doesn't match your "IsAPrime" function name as you return 'true' when the trial division modulo is zero showing that

**the test number can be factored**which should mean that

**the test number is not a prime**where this says IsAPrime = true . The full implementation of this would look something like the following to just count the number of primes up to the range:

bool IsAPrime(int n) { for(int i(2); i<=sqrt(n); i++) if(n%i == 0) return false; return true; } //must call the above over a range in order to do something #define MAX_NUM 1000000 int count = 0; for (int i = 2; i <= MAX_NUM; ++i) if (IsAPrime(i)) ++count;

Now perhaps due to errors it seems that 1.29 seconds with a 2.53 Gigahertz CPU is fairly slow at this as my Intel I7-2700K at 3.5 Gigahertz takes just 0.265 seconds to get the correct count of 78498 with full optimization enabled in code release mode, but perhaps the i7 performs integer divisions faster as that is mostly how the routine is spending its time - trial division remember - or perhaps you were running in a debug mode without full optimization turned on.

Your second example is indeed the true Sieve of Eratosthenes (unlike the OP's version which uses multiplication to determine the steps across the composite numbers to cull). However your routine also doesn't seem to do the job of sieving for primes up to a million as it has a fixed array size of 18000 rather than a million plus one (1,000,001); thus, I fail to see how you used this routine for timing. In fact, if you try to run this with a local array size of a million and one (1,000,001) four byte integers or even that many one byte chars it will fail due to trying to use too much stack space (four Megabytes/one Megabyte) and one will have to create the array as a global variable or malloc()/new it into heap space in order to get the routine to run. Also, I fail to see how your routine is any "simpler" than the last of my postings above for the Sieve of Eratosthenes, which I will reformat to have a similar calling signature as your routine as follows:

int EratosthenesSieve (int upper, unsigned char sieve[], int array[]) { /* the function takes the upper limit to which we test the numbers in the arguments, the sieving array, and the array in which we store the found primes, and it returns the exact number of primes found */ int num=0; memset(sieve, 1, MAX_NUM + 1); //make the logic so true means prime for (int i(2); i <= upper; ++i) { if(sieve[i]) { array[num++] = i; for (int tmp(i + i); tmp <= upper; tmp += i) sieve[tmp] = 0; //cull composite numbers to not a prime } } return num; }

I don't know how you managed to make this run as slow as 0.9 seconds as on my machine as above it runs

**in 0.00434 seconds!!!**

It is extremely easy and takes almost no code to add the improvement so that culling composite numbers starts at the square of the prime being culled and the highest prime used for culling is the square root of the maximum number in the range, trading one square root per run plus one multiply per base prime number less than the square root of the range for a considerable saving in time, as follows:

int EratosthenesSieve (int upper, unsigned char sieve[], int array[]) { /* the function takes the upper limit to which we test the numbers in the arguments, the sieving array, and the array in which we store the found primes, and it returns the exact number of primes found */ int num=0; memset(sieve, 1, MAX_NUM + 1); //make the logic so true means prime const int SQRT_LIMIT = (int)sqrt((double)upper); for (int i(2); i <= SQRT_LIMIT; ++i) { if(sieve[i]) { array[num++] = i; for (int tmp(i * i); tmp <= upper; tmp += i) sieve[tmp] = 0; //cull composite numbers to not a prime } } for (int i(SQRT_LIMIT + 1); i <= upper; ++i) if (sieve[i]) array[num++] = i; return num; }

This code takes about 0.00328 seconds on my machine as above.

As you say there are other techniques including improvements to this one that can reduce the execution time further, with the first thing to try to pre-eliminate the even numbers since two is the only even prime as I did in my second post in this thread (the first post with code) for a further reduction of almost a factor of two in culling composite number time and a possible reduction by about a factor of two in the required sieve array size.

Again, I fail to see how you think your routine is simpler than either of the two versions of the Sieve of Eratosthenes I had posted previously, which also are simple incarnations of the Sieve of Eratosthenes.