[erlang-questions] Prime numbers exercise from Project Euler
Jeremy Ong
jeremy@REDACTED
Tue Jul 23 22:48:10 CEST 2013
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
I did a very cursory look at your code and it seems your approach to
generating the primes is not very efficient. Also, I'd recommend
adding it as you go to save memory (rather than storing all 2 million
primes in memory and adding them at the end).
On Tue, Jul 23, 2013 at 7:47 AM, Damian Kösters
<koesters.damian@REDACTED> wrote:
> 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
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
More information about the erlang-questions
mailing list