[erlang-questions] beginner: Generating a list of prime numbers
Matthew Palmer
mpalmer@REDACTED
Fri Feb 6 07:18:08 CET 2009
On Thu, Feb 05, 2009 at 06:50:22PM -0800, Mark Wagner wrote:
> As a way of learning the basics of Erlang, I'm solving various
> problems from Project Euler (http://projecteuler.net/).
Well, that's kinda spooky -- so am I. <grin>
> 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?
You could use lists:reverse a couple of times to append the new value to the end
of the list, like so:
list_primes(lists:reverse([Candidate|lists:reverse(PrimesSoFar)])), ...);
You can also optimise a little further by only doing primality checking for
primes less than or equal to sqrt(Candidate), since if there's a factor F
greater than sqrt(Candidate) there must also be one less than it (Candidate
div F). For that to work, of course, you'd need to re-order your list to be
smallest first, and not use lists:any, but rather your own list-walking
function, to do the testing.
BTW, isn't Erlang a *good* language to do this sort of thing in? I'm loving
it, myself -- trivial to debug things, and the problems solve themselves so
quick (I'm fairly sure that I'm writing these Euler problems quicker than I
would in Ruby, my current favourite language).
- Matt
More information about the erlang-questions
mailing list