时间戳

首页 > 解决方案 > Prolog - 实施埃拉托色尼筛法的麻烦

prolog - Prolog - 实施埃拉托色尼筛法的麻烦

问题描述

我正在尝试在 prolog 中编写一个程序来查找所有质数到一个限制N，我正在尝试通过使用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已经实例化并且它的值不能改变。我曾尝试以其他方式解决此问题，但无法提出解决方案。

非常感谢任何帮助引导我朝着正确方向前进的帮助！

标签： prologsieve-of-eratosthenes

解决方案

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

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

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

推荐阅读