# [Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

Melissa O'Neill oneill at cs.hmc.edu
Fri Feb 23 00:27:15 EST 2007

```Bulat Ziganshin asked:
> but how it looks compared with classic C implementation of sieve
> algorithm?

two orders of magnitude slower, but remember that the Haskell
versions we'd looked at so far are able to incrementally produce a
list of primes of arbitrary length.

Andrew Bromage wrote:
> Just to fill out the implementations:
>
>     http://andrew.bromage.org/darcs/numbertheory/
>
> Math/Prime.hs has an implementation  of the Atkin-Bernstein sieve.

Cool, thanks.  When I ran your code trying to find the 10,000th
prime, I got
AtkinSieveTest: Ix{Integer}.index: Index (36213) out of range
((0,36212))

Here's the updated table...

------------------------------------------------------------------
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   -         -         -
Gale (#1)     0.12     17.99    -       -         -         -
"sieve" (#1)  0.16     32.59    -       -         -         -
"sieve" (#2)  0.01     32.76    -       -         -         -
Gale (#2)     1.36    268.65    -       -         -         -
------------------------------------------------------------------

Notes:
- Bromage is Andrew Bromage's implementation of the Atkin-Bernstein
sieve.  Like O'Neill (#2) and "sieve" (#3), asks for some upper limit
on the number of primes it generates.  Unlike O'Neill (#2) and
"sieve" (#3), it uses arrays, and the upper limit causes a large
initial array allocation.  Also, unlike the other Haskell algorithms,
it does not produce a lazy list; no output is produced until sieving
is complete
- C-Sieve is a "typical" simple implementation of the sieve in C
found with Google; it skips multiples of 2 and uses a bit array.
Also, obviously, it doesn't produce incremental output.

I've also updated the zip file of implementations at