[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