[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