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

[Richard O'Keefe]

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.
Using Prime_List ++ [New_Prime] will thus add O((log N)**2)) time
to your search, which must already be taking O(N) at least.

This is one of the few cases where List ++ [Element] makes sense.
>