Así que aquí está: estoy tratando de calcular la suma de todos los números primos por debajo de dos millones (paraeste problem), pero mi programa es muy lento. Sé que el algoritmo en sí mismo es terriblemente malo y de fuerza bruta, pero me parece mucho más lento de lo que debería.
Aquí limito la búsqueda a 20,000 para que el resultado no se espere demasiado.
No creo que este predicado sea difícil de entender, pero lo explicaré de todos modos: calculo la lista de todos los números primos por debajo de 20,000 y luego los sumo. La parte de suma está bien, la parte de primos es realmente lenta.

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

Me gustaría saber por qué es tan lento. ¿Es una buena implementación del estúpido algoritmo de fuerza bruta, o hay alguna razón que haga caer a Prolog?

EDIT: ya encontré algo, al agregar nuevos números primos en lugar de dejarlos en el encabezado de la lista, tengo números primos que ocurren con mayor frecuencia al inicio, por lo que es ~ 3 veces más rápido. Sin embargo, todavía necesito una idea:)