[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.)
Regards,
Alpar
More information about the erlang-questions
mailing list