[erlang-questions] generating primes

Imre Palik <>
Thu Oct 16 09:21:45 CEST 2008


> From: J?r?me Desquilbet <>
>
> Imre Palik a ?crit :
> > Hi,
> >
> > I am playing with Project Euler nowdays, and in the last few problems
> > I solved I had problems generating primes fast enough.  Currently I
> > am using the following implementation of the Sieve of Eratosthenes:
> >
> > sieve([]) -> []; sieve([H|T]) -> [H|sieve([X||X<-T,X rem H =/= 0])].
> >
> > ...
>
> Would you like a suboptimal algorithm?
> Here it is: N primes --> N sieves --> N erlang processes.
> It's all about playing after all... :-)
>    J?r?me.

Thanks for the idea.

Using 2 processes to partition the sieve I managed to get a 30% speedup in my dualcore machine on the first try.  I guess there must be an additional 10% somewhere that I can get wit fine tuning and/or with an additional process.

Imre



More information about the erlang-questions mailing list