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

[Richard O'Keefe]

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).