Prolog

Question

我正在尝试在 prolog 中编写一个程序来查找所有不超过限制 N 的素数，我正在尝试通过使用 Sieve of Eratosthenes 来实现这一点。我对 prolog 还很陌生，所以我还没有真正掌握递归思考的艺术（你可能会在我的代码中看到这一点）。

尽管如此，我（或多或少）尝试在 prolog 中实现该算法，但并没有像您在这里看到的那样走得太远：

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

Prolog - 实施 Eratosthenes 筛法时遇到问题

Prolog - Trouble with implementing the Sieve of Eratosthenes

sieve-of-eratosthenes