Prime number generation - speed comparison

"Efficient prime number generating" leads to some algorithms being displayed as "fast". Up to PG7.8 which does takes 65786 seconds to generate the prime numbers > 1.000.000.000.

Primesieve however does this in 0.2 seconds.

The system specifications used for the tests are a bit off. But I can imagine primesieve uses some highly advanced methods. Nonetheless, PG7.8 also seems optimized.

I haven't took the time to do the 10^9 test yet, but using Python I made a script doing the first 10.000.000 in under 60 seconds (edit: as of now 27 seconds). Again system specs cannot be compared, but my feeling says that my simple script is faster then PG7.8.

Sure enough however it isn't as fast as primesieve, but how would I go about comparing my method to some 'unoptimized' method? Is for instance AKS a way to go?

• AKS is for testing whether a given number is prime, quite a different task than finding all primes $< N$. Sep 8, 2014 at 1:04
• (1) the link is trying to optimize trial division for numbers 1-N, which will not be fast compared to sieves. (2) AKS is not a good idea here. (3) the RosettaCode task is misnamed -- it is not AKS and is a baroque way to do poor trial division. Sep 8, 2014 at 3:30

Some caveats on comparisons. If you time speed to print primes, you're going to be mostly timing the output routine speeds (hint: write your own number to ASCII routine to a buffer and use syswrite, for a very large speedup over printf). It's probably best to ignore printing unless that truly is your application. You do need to do some correctness testing at some point. Some of the algorithms really start separating themselves from the others once in $10^{10}$ to $10^{12}$ range -- lots of them will do the first 1 million trivially fast.
For actual speeds, of course computers differ, but primesieve generates and counts the first $10^9$ primes in slightly over 0.1 seconds on my machine using a single core, and all 12 of the segmented sieves (in C) I benchmark do it in under 1 second. Even a really basic 1-bit-per-odd 4-line-loop C program does it in 2.5 seconds.