[erlang-questions] Prime numbers exercise from Project Euler
Peer Stritzinger
peerst@REDACTED
Wed Jul 24 17:56:23 CEST 2013
On 2013-07-23 14:47:52 +0000, Damian Kösters said:
> primelist(Filterlist,Max,I) when I<Max
> -> primelist([X||X<-Filterlist,(X==I) or (X rem I /= 0)],Max,I+1);
> primelist([],Max,I)
> -> [];
This is no Sieve of Erasthotenes but rather trial division. That is
one reason why this is much slower than it needs to be.
See this answer for an explanation why it is no Sieve:
http://stackoverflow.com/a/389740/364327
(make sure to read the linked paper)
Also one speedup in your code would already be to only check until a
Max of sqrt(N).
Generally Sieve of Erasthotenes is not very fast as is to be expected
of a algorithm thats over 2000 years old ;.)
If you really looking for a fast sieve try
http://en.wikipedia.org/wiki/Sieve_of_Atkin
But I think Erasthotenes Sieve would be sufficiently fast if
implemented correctly.
More information about the erlang-questions
mailing list