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

Richard O'Keefe <>
Tue Feb 10 01:43:34 CET 2009


On 9 Feb 2009, at 7:49 pm, Alpár Jüttner wrote:
>> Brute force.  You test O(N) numbers, but find only O(log N) primes.
>
> There are much more primes than that.

Yes, typo.  I meant O(N/log N), and it's precisely the Prime
number theorem I was referring to.  The list of numbers to
be checked against only needs to grow to O(sqrt(N)).

In any case, the bulk of the checks are going to be against the
first few primes.  If you step through numbers in, say, blocks
of 30 (= 2*3*5), there are only 8 candidates in each block (the
others all being a multiple of 2, 3, or 5).




More information about the erlang-questions mailing list