[erlang-questions] Prime numbers exercise from Project Euler

Damian Kösters koesters.damian@REDACTED
Tue Jul 23 16:47:52 CEST 2013


Hi everyone,

I am new to Erlang and exercise by solving project-euler problems. The 
current one is this

*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.**Find the sum of 
all the primes below two million.*

I tried two approaches which work for small numbers but take way too 
long for larger inputs like 2 million. Is there anything to improve 
performance or is Erlang simply not made for problems like this?
I would be happy to get some feedback on my code. For example I am not 
sure if it is a developer's task to keep track of variables like Max in 
the second example. (I've only included this because it is not allowed 
to use functions inside guard expressions).


%1st approach:
%returns a lists of prime numbers smaller than N
%this works by eliminating non-prime numbers from the sequence(1,N) in N 
steps

    -module(primes).
    -export([primelist/1]).

    primelist(N) -> primelist(lists:seq(1,N),N,2).

    primelist(Filterlist,Max,I) when I<Max
         -> primelist([X||X<-Filterlist,(X==I) or (X rem I /= 0)],Max,I+1);
    primelist([],Max,I)
         -> [];
    primelist(Filterlist,Max,I) when I == Max
         -> Filterlist.


%2nd approach
%returns the sum of the primes up to N
%the function successively builds up a list of primes by testing candidates
%and sums it afterwards

    -module(prime9).
    -export([sumprimes/1]).

    sumprimes(N) -> sumprimes(N,[2],[2],2,3).

    sumprimes(N,[H|T],L,Max,Try) when (Max<N) andalso (Try rem H /= 0)
         -> sumprimes(N, T,L, Max, Try);
    sumprimes(N,[H|T],L,Max,Try) when (Max<N) andalso (Try rem H == 0)
         -> sumprimes(N, L,L, Max, Try+1);
    sumprimes(N,[2],L,Max,Try) when (Try rem 2 /= 0)
         -> sumprimes(N,[],L,Max,Try);
    sumprimes(N,[2],L,Max,Try) when (Try rem 2 == 0)
         -> sumprimes(N,L,L,Max,Try+1);
    sumprimes(N,[],L,Max,Try) when (Max<N)
         ->
    sumprimes(N,lists:append([Try],L),lists:append([Try],L),Try,Try+1);
    sumprimes(N,L,[H|T],Max,Try) when (Max >= N)
         -> lists:sum(T).


Thank you very much& best regards
Damian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130723/7da3684c/attachment.htm>


More information about the erlang-questions mailing list