Что является узким местом в этом предикате, связанном с простыми числами?
Итак, вот оно: я пытаюсь вычислить сумму всех простых чисел ниже двух миллионов (дляЭта проблема), но моя программа очень медленная. Я знаю, что сам по себе алгоритм ужасно плох и груб, но кажется мне он намного медленнее, чем следовало бы.
Здесь я ограничиваю поиск до 20000, чтобы результат не ожидался слишком долго.
Я не думаю, что этот предикат трудно понять, но я все равно объясню: я вычисляю список всех простых чисел ниже 20000, а затем суммирую их. Часть суммы в порядке, часть простых чисел действительно медленная.
problem_010(R) :-
p010(3, [], Primes),
sumlist([2|Primes], R).
p010(20001, Primes, Primes) :- !.
p010(Current, Primes, Result) :-
(
prime(Current, Primes)
-> append([Primes, [Current]], NewPrimes)
; NewPrimes = Primes
),
NewCurrent is Current + 2,
p010(NewCurrent, NewPrimes, Result).
prime(_, []) :- !.
prime(N, [Prime|_Primes]) :- 0 is N mod Prime, !, fail.
prime(ToTest, [_|Primes]) :- prime(ToTest, Primes).
Я хотел бы получить представление о том, почему это так медленно. Это хорошая реализация алгоритма глупой грубой силы, или есть какая-то причина, которая заставляет Пролог падать?
РЕДАКТИРОВАТЬ: я уже нашел что-то, добавляя новые простые числа вместо того, чтобы поместить их в начало списка, у меня есть простые числа, которые встречаются чаще при запуске, так что это ~ в 3 раза быстрее. Все еще нужно некоторое понимание, хотя :)