问题标签 [primality-test]

为了展示如何用卢卡斯序列检查素数，让我们看一个例子。考虑卢卡斯序列中的前几个数字：1,3,4,7,11,18,29,47,76,123,...

如果我们想知道一个特定的数字，比如 7，是否是素数，我们将卢卡斯数列中的第 7 个数字减去 1。第 7 个卢卡斯数是 29。减去 1，我们得到 28。现在，如果这个结果是能被 7 整除，7 可能是素数。在我们的示例中，28 可以被 7 整除，因此它可能是素数。我们称这些数为Lucas 伪素数。

如果我们对另一个数字感兴趣，比如 8，我们将取第 8 个卢卡斯数并减去 1。在这种情况下，我们得到 46，它不能被 8 整除。所以，8绝对不是素数。此方法对于过滤出合数很有用。

因此，确定整数p是否可能是素数的一般过程如下：

1. 找到第p个卢卡斯数
2. 减 1
3. 检查p是否将结果均分

定义一个 SCHEME 函数，命名(lucas-pseudoprime p)它使用这种方法来确定整数p是否是 Lucas 伪素数。

到目前为止我有这个：

不知道这有什么问题。

我有我认为是使用 Lua 的 miller-rabin 算法的正确实现，并且我试图获得素数的一致回报。看来我的实现只工作了一半。虽然如果我尝试在 python 中实现类似的代码，那么该代码 100% 的时间都有效。有人能指出我正确的方向吗？

我编写了下面的代码，以使 Lucas-Lehmer 级数达到 p，因为 p 是梅森数的指数。检查后我发现它不适用于某些素数 p，例如 11、23、29 等。任何帮助都将非常有价值！

这是代码：

我对如何计算时间复杂度有基本的了解，但由于素数的随机性，我不确定在这种情况下如何计算它。

快速解释 --> 本质上，我一直在计算余数，以便知道下一个素数是什么时候。

我的代码：

我有一个代码可以检查一个数字是否为素数，并相应地输出“是”或“否”。但是当我输入 1763 时，即使它不是素数，它也会输出“是”。该代码通过检查一个数字是否可以被 2 到 n-1 之间的任何数字整除来检查它是否是素数。所以当我输入 1763 时，它应该输出“No”，因为 1763 可以被 41 整除。我的代码出了什么问题？

我只能说逻辑一定包括图灵机中的乘法和除法逻辑。但实际上我无法找出确切的解决方案。

我有一个随机数数组，我必须从该数组中返回素数。我熟悉 root(n) 解决方案（n 是那个特定的数字而不是数组的大小）。我不能应用 Eratosthenes 的筛子，因为它适用于一定范围内的数字，但这里的数字是完全随机的。

如果我遗漏了什么，请纠正我。提前致谢！

我正在尝试使用递归检查数字是否为素数。我被要求使用递归辅助函数，但我不确定应该如何实现它。

我想我知道算法，但我从未尝试在 Racket 中使用递归辅助函数。这是我目前的想法：

1. 看看 n 是否可以被整除i = 2
2. 放i = i + 1
3. 如果i^2 <= n继续。
4. 如果没有i均分的值n，那么它一定是素数。

这是我目前所拥有的......

使用递归辅助函数的好方法是什么？

谢谢！

我有一个简单的问题：取一个数字并确定它是否是素数。我无法弄清楚为什么以下内容不起作用。

这返回真！我不知道为什么。

我正在尝试使用 AKS 算法对 16 位长的数字执行素数检查。我不断收到错误消息。有人可以编译我的代码并帮助我了解我在哪里犯了错误。（我要编译的数字示例：1425412525412545。）

这是我的 AKSPrime 课程：

这是我的 PolynomialArray 类：

这是我的 BigIntExtended 类：

我的第三课 TextReader：