[Haskell-cafe] Prime finding

[Melissa O'Neill]

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