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).