这个素数相关谓词的瓶颈是什么？

所以这里是：我正在尝试计算低于两百万的所有素数的总和（对于这个问题），但是我的程序非常慢。我确实知道该算法本身非常糟糕并且是一种蛮力算法，但对我来说它似乎比应有的速度要慢得多。
这里我将搜索限制为 20,000，这样结果就不会等待太久。
我不认为这个谓词很难理解，但无论如何我都会解释它：我计算 20,000 以下的所有素数的列表，然后对它们求和。求和部分很好，素数部分真的很慢。

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

我想了解一下为什么它这么慢。是愚蠢的暴力算法的良好实现，还是有某种原因导致Prolog失败？

编辑：我已经发现了一些东西，通过附加新的素数而不是让它们出现在列表的开头，我的素数在开始时出现得更频繁，所以速度快了约 3 倍。但仍然需要一些洞察力:)

首先，Prolog 不会在这里失败。

有很多非常聪明的方法来生成素数。但作为一个便宜的开始，只需以相反的顺序累积素数即可！ (7.9s -> 2.6s) 通过这种方式，较小的可以更快地进行测试。然后，考虑仅针对 141 以内的素数进行测试。更大的素数不能成为影响因素。

然后，您可以添加 3、5、7，而不是仅逐步遍历不能被 2 整除的数字。

有人就这个“问题”写论文。参见，例如这张纸，尽管对“真正的”算法到底是什么进行了有点复杂的讨论，22 世纪前，当算盘的最新版本被庆祝为萨拉米斯片.