読者です 読者をやめる 読者になる 読者になる

project euler problem 10 answer

区間ふるいを使ったらとけた。ひどいソース。

primes(Primes, Prime, NextPrimes) :-
        [Prime, _] = Primes,
        primes_next(Primes, NextPrimes).
primes_next([Prime, [Head, Appender]], NextPrimes) :-
        P1 is Prime + 1,
        (primes_is_prime(P1, Head, Appender),
         Appender = [P1 | Tail],
         NextPrimes = [P1, [Head, Tail]];
         primes_next([P1, [Head, Appender]], NextPrimes)).
primes_is_prime(P, Primes, Tail) :-
        [Head | Rest] = Primes,
        (P < Head*Head;
         P mod Head =\= 0, primes_is_prime(P, Rest, Tail)).
primes_is_prime(_, Tail, Tail).


primes_sum(BelowN, Sum) :-
        primes_new(Primes),
        primes_sum_sub(BelowN, Primes, 0, Sum).
primes_sum_sub(N, Primes, Acc, Sum) :-
        primes(Primes, Prime, NextPrimes),
        Acc1 is Acc + Prime,
        (primes_sum_is_middle(N, Prime),
         Next is Prime + 2,!,
         primes_sum_middle(N, Next, Primes, Acc1, Sum);
         primes_sum_sub(N, NextPrimes, Acc1, Sum)).
primes_sum_is_middle(N, Prime) :- sqrt(N) < Prime.
primes_sum_middle(N, Current, [_, [Primes, Tail]], Acc, Sum) :-
        primes_sum_middle_loop(N, Current, Primes, Tail, Acc, Sum).
primes_sum_middle_loop(N, Current, Primes, Tail, Acc, Sum) :-
        N > Current,
        Next is Current + 2,
        (primes_is_prime(Current, Primes, Tail) ->
         (Acc1 is Acc + Current, primes_sum_middle_loop(N, Next, Primes,Tail, Acc1, Sum));
         primes_sum_middle_loop(N, Next, Primes,Tail, Acc, Sum)).
primes_sum_middle_loop(_,_,_,_, Acc, Acc).

problem10(Result) :-
        primes_sum(2000000, Result).