1
$\begingroup$

"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?

$\endgroup$
2
  • 1
    $\begingroup$ AKS is for testing whether a given number is prime, quite a different task than finding all primes $< N$. $\endgroup$ Sep 8, 2014 at 1:04
  • 1
    $\begingroup$ (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. $\endgroup$
    – DanaJ
    Sep 8, 2014 at 3:30

1 Answer 1

2
$\begingroup$

Kim gives some good basic examples at the primesieve site. These are pretty good benchmarks of a decent very simple sieve in C/C++. The method used in your link is very inefficient -- he's trying to optimize the trial division used for each number. This is not the right way to do this task at all (and AKS would just make things much worse).

For simple unoptimized code, with additional examples showing mild optimizations, see Rosetta Code. You can find examples in whichever language you'd like.

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.

For Python, I recommend looking at the excellent SoE's from Robert William Hanks. His primes2 method is quite fast, and the numpy version faster yet. It generates and counts the first 10M primes in under 0.2s on my machine, 100M in 1.5s, 1000M in 19 seconds. For Perl, the odds-only string sieve on RosettaCode is about 3x slower but that's still not too bad. One can segment them for better performance at the large sizes.

$\endgroup$
1
  • $\begingroup$ Thanks for clearing up. I'm not used to Python as much as I'd like, for instance I need to do some things in parallel which is a bit hard after one day :). But the timing of methods and printing to the console seems to be separated (as in timeit seems to ignore printing times). I can now calculate the first 10M in a little over a second. $\endgroup$
    – Ropstah
    Sep 8, 2014 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.