问题标签 [primality-test]

我如何使用蛮力（朴素算法）检查一个 16 位长整数是否为素数并打印它之前的所有素数。号码示例：1254786951475276。这是我的代码：

https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/

// 一个优化的基于学校方法的 C++ 程序来检查 // 如果一个数字是素数

我期待使用逻辑运算符和关系运算符检查 3 位数字是否为素数。该数字使用 3 个变量表示，其中 7-1 位设置为 0，只有位置 0 上的位是实际数据。假设我们有：

可以假设素数是一个函数，如果该数是素数则f输出，否则。10

如何使用尽可能最优的按位运算（逻辑运算符）来解决这个问题？可以假设可以从真值表的 KV 图中提取最小合取/析取形式。

如何使用关系运算符解决这个问题？

哪个会更快？

一些有用的数据：

SICP 练习 1.28

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-ZH-11.html#%_thm_1.28

费马测试的一种变体被称为 Miller-Rabin 测试（Miller 1976；Rabin 1980）。这从费马小定理的另一种形式开始，该定理指出如果 n 是质数并且 a 是任何小于 n 的正整数，则 a 的 (n - 1) 次幂等于 1 模 n。为了通过 Miller-Rabin 检验测试数字 n 的素数，我们选择一个随机数 a < n 并使用 expmod 过程将 a 提高到 (n - 1) 次幂模 n。然而，每当我们在 expmod 中执行平方步骤时，我们都会检查我们是否发现了“1 模 n 的非平凡平方根”，即一个不等于 1 或 n - 1 的数，其平方等于1 模数 可以证明，如果存在这样一个 1 的非平凡平方根，则 n 不是素数。如果 n 是一个非素数的奇数，那么，对于至少一半的数字 a < n，以这种方式计算 a^(n-1) 将揭示一个模数为 n 的非平凡平方根。（这就是为什么 Miller-Rabin 测试不能被愚弄的原因。）修改 expmod 过程以发出信号，如果它发现 1 的非平凡平方根，并使用它来实现 Miller-Rabin 测试，过程类似于 fermat-test。通过测试各种已知的素数和非素数来检查你的程序。提示：产生 expmod 信号的一种方便方法是让它返回 0。

我已经编写了自己的解决方案，其结果与此处提供的解决方案一致：

http://community.schemewiki.org/?sicp-ex-1.28

15是一个非素数的奇数，因此对于a从1到的至少一半数字14，我预计计算expmod(a, 14, 15)将显示 1 模 n 的非平凡平方根，这由expmod返回表示0。

但是，这些是我得到的结果：

可以看出，这些结果中只有 2 个是0，与预期的至少 7 个相差甚远。

我误解了声明吗？我是一个彻头彻尾的白痴吗？代码错了吗？SICP错了吗？非常感谢。

编辑 1：要求我提供我正在使用的确切代码。就是这样，虽然我本质上只是复制我链接到的解决方案，并使用别名remainder，mod因为这就是我的解释器所说的。

编辑 2：我现在还手动计算了从 1 到 14的所有值的步骤（它总是通过, , , , , ,expmod(a, 14, 15)递归），我确信只有并遇到一个非平凡的平方根 1。所以我倾向于认为 SICP 对此要么是错误的，要么是没有清楚地表达自己。exp = 14exp = 7exp = 6exp = 3exp = 2exp = 1exp = 0aa = 4a = 11

费马测试的一种变体被称为 Miller-Rabin 测试（Miller 1976；Rabin 1980）。这从费马小定理的另一种形式开始，该定理指出如果n是质数并且a是小于n的任何正整数，则a的(n - 1)次幂等于1模n。

为了通过 Miller-Rabin 检验来测试数字n的素数，我们选择一个小于n的随机数a并使用该过程将a提高到( n - 1) st 次幂模数。但是，每当我们在 中执行平方步骤时，我们都会检查是否发现了“ 1模n的非平凡平方根”，即一个不等于1或n - 1的数，其平方等于1模n .expmodexpmod

可以证明，如果存在这样一个1的非平凡平方根，则n不是素数。还可以证明，如果n是一个非素数的奇数，那么对于至少一半的数字a < n，以这种方式计算a ^n-1将揭示1模n的非平凡平方根。（这就是为什么 Miller-Rabin 测试不能被愚弄的原因。）

如果发现1expmod的非平凡平方根，则修改该过程以发出信号，并使用该过程以类似于 的过程来实现 Miller-Rabin 检验。通过测试各种已知的素数和非素数来检查你的程序。提示：产生信号的一种方便方法是让它返回 0。fermat-testexpmod

这就是我到目前为止所拥有的。

我认为我实施miller-rabin正确，但我不明白修改后expmod的工作方式。你检查正方形之前的数字还是正方形之后的数字？我不知道从阅读问题。

一个月以来，我一直在阅读一本具有竞争力的编程书籍。这本书是由我国（孟加拉国）的世界决赛选手之一撰写的。需要指出的是，这本书是用我们的母语（孟加拉语）写的，在世界范围内并不那么受欢迎。因为有孟加拉语的内容，我不能在这里引用它。这就是为什么我首先感到抱歉。

在那本书的数论章节中，给出了许多算法来测试素性。他展示的最优化的是 O(nloglogn) 中的“Eratosthenes 筛”。但他写了一行。我正在翻译它。“有一种更有效的方法来测试 O(logn) 中的素数。自己想一想。如果你没有完成，那就用谷歌搜索吧！！”

我用谷歌搜索了它。但我没有找到任何令人满意的东西。

真的可以在 O(logn) 中测试一个数字的素数吗？如果有可能，那么可以得出哪个范围？

我有一个接受最多 10 位整数的素数测试代码，但我想扩展它，以便代码接受超过 200 位数字。我应该在代码中切换什么？

我创建了一个简单的素数测试算法，但是对于像 15 这样的数字它失败了。为什么？

我尝试了一个带有其他变体的 elif 语句，但它仍然不起作用：

任何帮助表示赞赏。

我创建了一个素数测试算法，但它不起作用。

本质上，这些是我的程序采取的步骤：

• 询问用户寻找素数的下限和上限
• 一个数组，素数，将存储我的素数
• 嵌套的 for 循环；第一个for loop取用户下限和上限之间的每个数字，然后检查这些数字中的每一个是否可以被 2 和用户上限之间的任何数字整除
• 如果上下界之间的任何数都可以被 2 和用户的上界之间的任何数整除，则该数显然不是素数。
• 否则，将数字附加到数组素数：

但是，无论一个数字是否为素数，该函数总是输出 no，但我不知道为什么！

我有一个程序可以通过将大数存储为字符串来计算它们，这样我就可以拥有超过 long long 的非常大的数字。

我可以使用我编写的一个函数来添加字符串，该函数模拟我们人类如何在纸上手动进行加法，并且它有效。我能够准确地将大的“字符串整数”加在一起，即使它们有数百个数字。

我现在想用它来枚举大量数字并测试素数。问题是，我不知道如何在非常大的 string-int 上执行此操作，因为我无法将其转换为 long long 然后执行测试。

是否有测试素数的技术可以对数字的数字或其他东西起作用？我将如何尝试分解表示为字符串的大数字，并测试数字是否是它的因子等？我该如何解决这个问题？