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

Hynek Vychodil <>
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
> 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.
>
> I.
> _______________________________________________
> erlang-questions mailing list
> 
> http://www.erlang.org/mailman/listinfo/erlang-questions
>



-- 
--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...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20090206/1a15dac1/attachment.html>


More information about the erlang-questions mailing list