Project Euler 10: Summation of primes

Vi har tidigare sett problem som rör primtal men problem 10 är det första problemet där mängden primtal är så pass stort att algoritmen för att finna primtalen måste vara riktigt effektiv.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Här gäller det att tänka på alla tal som man inte behöver söka igenom. 2 är det enda jämna primtalet så därför kan vi testa talen 3+N där N är ett jämt tal och addera specialfallet 2. Eftersom inga av talen är jämna behöver man bara kolla ifall de är delbara med tal upp till deras kvadratrot. Dessa begränsning i kombination med någon form av primtalshov kan lösa problem 10 på 1.29 sekunder.

problem_10() ->
    Start = os:timestamp(),
    Res = primes(lists:seq(3, 2000000,2)) + 2,
    io:format("Resultatet: ~p och det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]).
 
primes([H|T]) when H > 1415 -> H + lists:sum(T);
primes([H|T]) -> 
    Sieved = [X || X <- T, X rem H =/= 0], 
H + primes(Sieved). 

länk till koden

Mvh;

André Le Blanc