[erlang-questions] beginner: Generating a list of prime numbers
Richard O'Keefe
<>
Mon Feb 9 01:55:46 CET 2009
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.
>
More information about the erlang-questions
mailing list