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 <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a><br>
<br><div class="gmail_quote">On Fri, Feb 6, 2009 at 12:23 PM, Imre Palik <span dir="ltr"><<a href="mailto:imre@u-tx.com" target="_blank">imre@u-tx.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
As for the primes:<br>
<br>
sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0])];<br>
sieve(L, _) -> L.<br>
<br>
call it as:<br>
<br>
Primes = [2|sieve(lists:seq(3, N, 2), math:sqrt(N))],<br>
<br>
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.<br>


<br>
BTW for such things the project euler forum si your friend.<br>
<br>
<br>
From: Matthew Palmer <<a href="mailto:mpalmer@hezmatt.org" target="_blank">mpalmer@hezmatt.org</a>><br>
<div><br>
> BTW, isn't Erlang a *good* language to do this sort of thing in?  I'm loving<br>
> it, myself -- trivial to debug things, and the problems solve themselves so<br>
> quick (I'm fairly sure that I'm writing these Euler problems quicker than I<br>
> would in Ruby, my current favourite language).<br>
<br>
</div>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.<br>


<font color="#888888"><br>
I.<br>
</font><div><div></div><div>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>--Hynek (Pichi) Vychodil<br><br>Analyze your data in minutes. Share your insights instantly. Thrill your boss.  Be a data hero!<br>Try Good Data now for free: <a href="http://www.gooddata.com" target="_blank">www.gooddata.com</a><br>