Prolog - 实施埃拉托色尼筛法时出现问题

Question

我正在尝试在序言中编写一个程序，查找所有素数达到极限N，我试图通过使用埃拉托斯特尼筛法来实现这一点。我对序言非常陌生，所以我还没有真正掌握递归思考的艺术（你可能可以在我的代码中看到这一点）。

尽管如此，我（或多或少）尝试在序言中实现该算法，但并没有达到您将在此处看到的程度：

 allPrimes(N, Primes) :-
     numlist(2, N, Numlist),
     A is round(sqrt(N)),
     foreach(between(2, A, _i), sift(_i, Numlist, Primes)).

 sift(_i, Numlist, Primes) :-
     findall(_j, (member(_j, Numlist), _j \== _i, (_j mod _i =:= 0)), L),
     subtract(Numlist, L, Primes).

我不断获得false输出，因为subtract(Numlist, L, Primes)失败，我猜测它失败的原因是因为Primes它已经被实例化并且它的值无法更改。我尝试过用其他方式解决这个问题，但无法想出解决方案。

非常感谢任何指导我正确方向的帮助！

Answer 1

实例化后，您无法更改素数列表。但是，如果它们未实例化（不是您的情况），您可以进一步实例化其中的某些项目，并且您可能可以通过这种方式解决此问题。

这是基于您的算法的递归解决方案：

allPrimes(N, Primes) :-
    numlist(2, N, Numlist),
    Stop is round(sqrt(N)),
    allPrimes(Numlist, Stop, Primes).
    
allPrimes([N|Numlist], Stop, [N|Primes]):-
  exclude(is_multiple(N), Numlist, MPrimes),
  (N =< Stop -> allPrimes(MPrimes, Stop, Primes) ; Primes=MPrimes).
  
is_multiple(N, I):-
  I mod N =:= 0.

因此，您构建一个可能的整数列表并计算停止数。然后调用递归过程allPrimes/3，该过程获取第一个素数，然后从列表中排除该数字的所有倍数，并使用剩余元素递归调用自身。完成递归后（基本情况是当 N 是停止数时），我们重建素数列表。

示例运行：

?- allPrimes(100, Primes).
Primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].