问题标签 [primality-test]

这是代码，其中limit = 8：

输出：

它只返回第一个5而不是，8我不知道为什么。

更新：

它正在跳过从 13 开始的所有索引。我怀疑错误出现在isMersenneLucasLehmer(unsigned int). 我已经盯着太久了，找不到它。

我对 LISP 非常陌生，并且正在解决一些初学者问题。我尝试定义 ISPRIME 函数，但它似乎无法正常工作。这是我的代码：

但是在运行我的代码时，我以值 5 为例：

5 应该是质数。我怀疑一切都落入了： (if (= (mod nd) 0) 语句不应该出现的情况。d 应该继续递减直到达到 0 并返回 true，但事实并非如此。我似乎无法看看我的逻辑错误发生在哪里。

非常感谢任何和所有帮助！

你好我已经创建了这个程序来检查一个数字是否是一个素数。它有效，但由于某种原因说 999 是质数。我的错在哪里。如果有人解释，那就太好了。谢谢你！

这是我的程序：

我想知道这个程序如何知道一个数字是否是素数。我知道它会检查余数以找到要除以的偶数，但它怎么知道一个数字只有 2 个因数？我是递归概念的新手，所以对这些步骤的解释会很有帮助，谢谢。

代码

资源

https://github.com/hydrogeologist/LearningPython/blob/master/_recursion%20example%20in%20Python

线路：184 至 194

I encountered two types of Miller Rabin primality test methods suddenly. One which uses randoms and another does not use randoms.

Is there a hidden random generation inside the second one or what? Thank you.

哥德巴赫猜想：每一个大于 2 的正偶数都是两个素数之和。例如 28（5,23 和 11,17）

我希望 Prolog 代码打印在下面（所有组合）：

我有一个打印单个组合 [5,23] 的代码，但不是下一个 [11,17]。

众所周知，要检查数字“n”是否为素数，我们只需要检查它是否具有小于 n 平方根的因数。

我的问题是检查所有小于 n 平方根的素数是否足够。

给定 n，找到 m 使得 m 是大于 n 的最小半素数。

下一个素数非常简单，半素数就不那么简单了。需要明确的是，只需要半素数，尽管同时获取因子会很方便。

我已经想到了一些方法，但我相信还有更好的方法。

算术运算假定为 O(1)。我使用了埃拉托色尼筛，这是 O(n log log n)，我知道阿特金筛，但我喜欢我的半优化 Eratosthenes。

1.从n开始数

从 n 开始数，当你找到一个半素数时停止。

这看起来真的很愚蠢，但如果有一个 O(log n) 半素数测试或 O(1) 测试给定下面的素数，这可能比其他 2 更快。

半素数分布似乎远高于素数分布，因此通过良好的半素数测试，这实际上可能比 O(n) 更好。

2. 素数倒计时

定义 prev(x) 和 next(x) 并分别给出前一个和下一个素数，如果素数存储在树中或使用列表二进制搜索，则可以是 O(log n)。

先做筛子。

从 p=prev(sqrt(n)) 和 q=next(n/p) 开始。当 pq<=n 时，转到下一个 q。如果 pq 小于迄今为止的最小值，则将其记录为新的最小值。继续前一个 p 直到您用完 p 进行测试。

这可以保证找到正确的答案，但速度相当慢。尽管如此，仍然是 O(n log n)，所以也许可以接受。

3. 素数计数

像往常一样从筛子开始。为 O(1) 素数测试创建筛子的哈希集视图。

从 p=2 开始。遍历素数直到 sqrt(n)。对于每个 p，得到 q=((((n/p+1)/2)*2)+1=((((n/p+1)>>1)<<1)|1。虽然 pq 小于迄今为止的最小值并且 q 不是素数，但将 2 添加到 q。如果 pq 仍然小于最小值，则将其记录为新的最小值。

我在 Java 中实现了 #1 和 #3，它们都使用了相同的 Sieve of Eratosthenes 实现。大部分运行时间都花在筛分上，所以如果要进行优化，它就在筛子中。经过一些优化后，向上计数 (#1) 击败了向上计数 (#3) 的素数，在最后一个也是最大的测试（11 个十进制数字 n）中速度是两倍。

不过仍有希望，因为筛子需要延伸多远取决于要进行主要测试的最大数量。如果存在具有较低质数测试界限的半质数测试，则计数方法可能会更快。

肯定有更好的算法吗？或者至少是一种更好的方法来实现这个？

我正在尝试在 C99 中实现Miller-Rabin 素数测试，但我遇到了一些问题来让它工作。我制作了一个小型测试集来验证实现是否有效，这就是我检查素数的方式

从列出的数字中，预期的输出将是

不; 不; 是的; 是的; 不; 是的; 不; 是的; 不; 是的; 不;

但是，作为实施，我得到的输出如下：

不; 不; 是的; 是的; 不; 是的; 不; 不; 不; 不; 不;

这是我编写算法的方式

我究竟做错了什么？为什么对“大”素数的测试失败，但对非常小的素数有效？我该如何解决这个问题？

我有一个 2500 位整数，我需要确定它的素数。R中有许多方法可以测试“小”数的素数，但该语言似乎不适合存储大量数字。有一些包旨在存储这些数字，但它们似乎都围绕着将它保存在一个字符串中，这让我不确定如何对其进行素数测试。任何有关该主题的语言功能的澄清将不胜感激。