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

Alpár Jüttner alpar@REDACTED
Mon Feb 9 07:49:40 CET 2009

On Mon, 2009-02-09 at 13:55 +1300, Richard O'Keefe wrote:
> On 6 Feb 2009, at 3:50 pm, Mark Wagner wrote:
> > The problem with this is that the list of prime numbers is ordered
> > largest-first, so that the small primes (the ones most likely to be
> > factors of a given number) are tested last.  This makes the
> > sophisticated solution slower than the naive one, which tests small
> > factors first.  Any suggestions on how to fix this?
> Brute force.  You test O(N) numbers, but find only O(log N) primes.

There are much more primes than that.
(According to the "Prime number theorem", there are around N/lnN primes
less then N.)


More information about the erlang-questions mailing list