问题标签 [primality-test]

代码：

该程序基于关于素数的费马定理。N 是要作为素数进行测试的数。该程序未显示“11”的正确结果。也许是由于我没有发现的一些错误。

我有以下代码确定数字是否为素数：

如何确定此函数的大 O 时间复杂度？在这种情况下，输入的大小是多少？

从http://www.haskell.org/haskellwiki/Testing_primality，有这个代码：

其中 primes 是素数列表（可能是无限的）。

两个问题：

1. 如何读取传递给foldr函数的 lambda
2. 既然foldr从右边开始，为什么这个函数在传递一个无限的素数列表时会起作用？我猜lambda中内置了短路？

我正在尝试学习 lisp，但我在质数方面遇到了一些困难。我需要一个函数is-prime，如果它是素数，我必须返回t，如果不是，我必须返回nil。

到目前为止，我有：

但我在那里有 2 个参数，我不知道如何只使用一个。另外，它根本不起作用。谁能帮我这个？谢谢！

我似乎无法使用此代码生成随机素数，有人可以帮助我吗？

我正在用 C++ 编写 cplex 音乐会技术。当我解决原始问题时（使用原始单纯形，对偶单纯形或内点，方法不重要），我是否可以提取解值，例如如果对偶问题是无界的，则可以提取对偶变量的极值射线值，或者如果对偶变量的最优解值对偶问题有最优解？

哪一组证人足以让 Miller-Rabin 检验对 10¹⁸ 以内的所有数字都正确？我知道使用不超过 17 的素数作为见证足以满足 n < 341550071728321。

我想写一个谓词来确定一个数字是否是素数。我通过蛮力 O(sqrt(n)) 算法来做到这一点：

1) 如果 number 为 2，则返回 true 并且不再检查任何谓词。

2）如果是偶数，返回false，不再检查谓词。

3) 如果数不是偶数，检查数的除数直到平方根。请注意，我们只需要检查从 3 开始的奇数除数，因为如果我们进入程序的这一部分，则数字不是偶数。在第 2 步中消除了偶数。

4) 如果我们找到一个偶数除数，则返回 false 并且不检查其他任何内容。

5）如果我们检查的除数​​大于数字的平方根，返回true，我们没有找到除数。不再进行谓词检查。

这是我的代码：

我遇到了问题。例如，如果我查询 prime(1)。该程序仍在检查除数。我以为添加'！将使程序停止检查先前条件是否为真。有人可以告诉我为什么程序会这样做吗？请记住，我是新手，我知道代码可以简化。但是，任何提示将不胜感激！

因此，我试图仅使用一个谓词来确定一个数字是否为素数。我真的不明白为什么这里的每个数字都被宣布为假。

我编写了以下程序，如果一个数字是素数，则返回 1，如果它是合数，则返回 0。虽然有可能错误地将复合物识别为素数。我想要关于改进（降低）以下算法的时间复杂度的建议。