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

[Steven Edwards]

Mark,

You can use lists:append(List, [Term]) to add larger primes to the back of
the list, but I'd suggest approaching your problem in a different way: N is
prime if the GCD of ((N-1)!, N) is 1.  Write a GCD function and use an
accumulator to store the FactorialSoFar.

If you need any hep, let me know.

Steven



> Message: 2
> Date: Thu, 5 Feb 2009 18:50:22 -0800
> From: Mark Wagner <carnildo@REDACTED>
> Subject: [erlang-questions] beginner: Generating a list of prime
>        numbers
> To: erlang-questions@REDACTED
> Message-ID:
>        <31073ef90902051850h2377c242s9f25d39ff47c6166@REDACTED>
> Content-Type: text/plain; charset=UTF-8
>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20090206/c17825e6/attachment.htm>