[erlang-questions] beginner: Generating a list of prime numbers

Imre Palik imre@REDACTED
Fri Feb 6 12:23:39 CET 2009

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 <mpalmer@REDACTED>

> BTW, isn't Erlang a *good* language to do this sort of thing in?  I'm loving
> it, myself -- trivial to debug things, and the problems solve themselves so
> quick (I'm fairly sure that I'm writing these Euler problems quicker than I
> 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.


More information about the erlang-questions mailing list