Ruben Zilibowitz wrote:
I see that there has been some discussion on the list about prime finding algorithms recently. I just wanted to contribute my own humble algorithm:
Thanks!
Comparing it to some of the algorithms in: http://www.haskell.org/pipermail/haskell-cafe/2007-February/ 022765.html
It seems to perform reasonably well. It also has the advantage of being quite short.
I've added it to my table. It's fun to find new ways to figure out primes, but I think the "shortness advantage" goes to the naive primes algorithm, which is faster and shorter. Melissa. ------------------------------------------------------------------ Time (in seconds) for Number of Primes ---------------------------------------------------- Algorithm 10^3 10^4 10^5 10^6 10^7 10^8 ------------------------------------------------------------------ C-Sieve 0.00 0.00 0.01 0.29 5.12 88.24 O'Neill (#2) 0.01 0.09 1.45 22.41 393.28 - O'Neill (#1) 0.01 0.14 2.93 47.08 - - Bromage 0.02 0.39 6.50 142.85 - - "sieve" (#3) 0.01 0.25 7.28 213.19 - - Naive 0.32 0.66 16.04 419.22 - - Runciman 0.02 0.74 29.25 - - - Reinke 0.04 1.21 41.00 - - - Zilibowitz 0.02 2.50 368.33 - - - Gale (#1) 0.12 17.99 - - - - "sieve" (#1) 0.16 32.59 - - - - "sieve" (#2) 0.01 32.76 - - - - Gale (#2) 1.36 268.65 - - - - ------------------------------------------------------------------