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 - - - -
------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
