[erlang-questions] beginner: Generating a list of prime numbers
Mark Wagner
carnildo@REDACTED
Fri Feb 6 03:50:22 CET 2009
As a way of learning the basics of Erlang, I'm solving various
problems from Project Euler (http://projecteuler.net/). Problem #10
involves generating a list of prime numbers. The naive solution to
this is to generate a list of numbers and test each of them
individually to see if it's prime; a more sophisticated solution uses
the list of primes already found to speed up the testing. My code for
the sophisticated solution is:
is_prime(PrimesSoFar, Candidate) -> not lists:any(fun(X) -> Candidate
rem X =:= 0 end, PrimesSoFar).
list_primes(PrimesSoFar, Max, Candidate) when (Candidate > Max) -> PrimesSoFar;
list_primes(PrimesSoFar, Max, Candidate) ->
case is_prime(PrimesSoFar, Candidate) of
true -> list_primes([Candidate|PrimesSoFar], Max, Candidate + 2);
false -> list_primes(PrimesSoFar, Max, Candidate + 2)
end.
list_primes(N) when N < 2 -> [];
list_primes(2) -> [2];
list_primes(N) -> list_primes([2], N, 3).
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?
--
Mark Wagner
More information about the erlang-questions
mailing list