[erlang-questions] beginner: Generating a list of prime numbers
Fri Feb 6 15:39:46 CET 2009
I should like notice that your algorithm is not The Sieve of Eratosthenes.
For example in sieve algorithm should not be 'rem' operation but just '+'.
For more details see http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
On Fri, Feb 6, 2009 at 12:23 PM, Imre Palik <> wrote:
> As for the primes:
> sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0])];
> sieve(L, _) -> L.
> call it as:
> Primes = [2|sieve(lists:seq(3, N, 2), math:sqrt(N))],
> You could also do it with tail recursion, but if N>10^6 the speedup is
> negligible. The real morale of the thing is that you want to use list
> comprehension whenever you can. It tends to be much faster than recursion.
> BTW for such things the project euler forum si your friend.
> From: Matthew Palmer <>
> > BTW, isn't Erlang a *good* language to do this sort of thing in? I'm
> > it, myself -- trivial to debug things, and the problems solve themselves
> > quick (I'm fairly sure that I'm writing these Euler problems quicker than
> > would in Ruby, my current favourite language).
> It depends on your definition of good. You won't be able to brute force
> anything. Not even those that you could in TCL. Sometimes even the optimal
> algorithm will run for several minutes. Also, if you try to use gb_trees
> for memo in dynamic programming, programming, it becomes really damn slow
> after a few million entries.
> erlang-questions mailing list
--Hynek (Pichi) Vychodil
Analyze your data in minutes. Share your insights instantly. Thrill your
boss. Be a data hero!
Try Good Data now for free: www.gooddata.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the erlang-questions