[Haskell-cafe] Prime finding

[Stephen Forrest]

On 2/22/07, Ruben Zilibowitz <r.zilibowitz at student.unsw.edu.au> 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:
[snip]
> 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.

It has the advantage of conciseness, and for small enough examples
will give reasonable results, though computing O(n/log(n)) gcds can be
very expensive.

One suggestion I would make is to build the list in reverse order.
Since the test proceeds through the list from left to right, and an
arbitrary positive integer is more likely to be divisible by a small
primes than a larger one, this ought to produce a faster result when
the input is composite.

Steve