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

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