如何检查一个数字是否为素数(check if a number is prime)

素数是那些只能被自身和1整除的数；所有其他的都被称为复合数。虽然有很多方法可以测试首要性，但也有权衡。完美的测试是存在的，但是对于大量的测试来说速度非常慢，而更快的测试可能会给出错误的结果。这里有几个选项可供选择，具体取决于您测试的数字有多大。...

第1部分第1部分，共3部分：基本测试

注：在所有公式中，n是测试素性的数字。

1分庭试验。从2到楼层（n{\displaystyle{\sqrt{n}}}）除以每个素数。
2费尔马小定理。警告：即使是a的所有值，也可能出现误报。请为a选择一个整数值，使其为2≤ A.≤ n-1。如果an（mod n）=a（mod n），那么n很可能是素数。如果这不是真的，n就不是素数。用不同的a值重复，以增加对素数的信心

Image titled Check if a Number Is Prime Step 2

3米勒-拉宾试验。警告：a的多个值可能出现误报，但很少出现。查找s和d的值，使n−1=2秒∗d{\displaystyle n-1=2^{s}*d}。选择一个整数值，使其等于2≤ 一≤ n-1。如果ad=+1（mod n）或-1（mod n），那么n可能是素数。跳到测试结果。否则，请转至下一步。将你的答案（a2d{\displaystyle a^{2d}）平方。如果这等于-1（mod n），那么n可能是素数。跳到测试结果。否则重复（a4d{\displaystyle a^{4d}等），直到a2s−1d{\displaystyle a^{2^{s-1}d}。如果你将一个非±1{\displaystyle\pm 1}（mod n）的数字平方，并以+1（mod n）结束，那么n不是素数。如果a2s−1d≠±1{\displaystyle a^{2^{s-1}d}\neq\pm 1}（mod n），则n不是素数。测试结果：如果n通过测试，用不同的a值重复以增加可信度。。

Image titled Check if a Number Is Prime Step 3

$n-1=2^{s}*d$

$a^{{2d}}$

$a^{{4d}}$

$a^{{2^{{s-1}}d}}$

$\pm 1$

$a^{{2^{{s-1}}d}}\neq \pm 1$

第2部分第2部分，共3部分：理解基本测试

1了解审判分庭法。根据素数的定义，只有当n不能被2或更大的整数平均除时，n才是素数。给出的公式通过删除不必要的测试（例如，测试3后，无需测试9）来节省时间。楼层（x）将x四舍五入到最接近的整数≤ 十、
2理解模运算。“x mod y”运算（modulo的缩写）意味着“将x除以y，然后找到余数”换言之，在模运算中，数字在达到某个特定值（称为模）时“环绕”回零。一个时钟以12模计数：它从10到11再到12，然后再回到1。许多计算器都有一个mod按钮，但请参阅本节末尾，了解如何手动求解大数。

Image titled Check if a Number Is Prime Step 5

我们知道费马小定理的陷阱。所有未通过此测试的数字都是复合数（非素数），但不幸的是，通过此测试的数字只可能是素数。如果您想确保避免误报，请在“卡迈克尔数”（每次都通过此测试）和“费马伪素数”（仅对a的某些值通过此测试）列表中查找n。

Image titled Check if a Number Is Prime Step 6

4尽可能使用米勒-拉宾试验。虽然手工测试很乏味，但这种测试通常在软件中使用。与费马的方法相比，这可以以实际的速度进行，并且给出的误报更少。一个复合数对A的值中的¼个以上不会给出假阳性。如果你随机选择A的几个值，并且它们都通过了这个测试，你可以相当有信心n是素数。

Image titled Check if a Number Is Prime Step 7

5对大数执行模运算。如果您无法使用带有mod功能的计算器，或者如果您的计算器无法显示那么高的数字，请使用指数属性和模运算来简化此过程。下面是350{\displaystyle 3^{50}mod 50的一个例子：用更易于管理的指数重写表达式：（325）∗325）{\displaystyle（3^{25}*3^{25}）mod 50。（如果手工计算，可能需要进一步细分）。(325∗325{\displaystyle（3^{25}*3^{25}）mod 50=（325{\displaystyle（3^{25}）mod 50∗325{\displaystyle*3{25}mod 50）mod 50。（这是模乘的一个性质。）325{\displaystyle 3^{25}mod 50=43。（325{\displaystyle（3^{25}}mod 50∗325{\displaystyle*3^{25}mod 50）mod 50=（43∗43）{\displaystyle（43*43）}mod 50=1849{\displaystyle=1849}mod 50=49{\displaystyle=49}。

Image titled Check if a Number Is Prime Step 8

$3^{{50}}$

$(3^{{25}}*3^{{25}})$

$(3^{{25}}$

$*3^{{25}}$

$3^{{25}}$

$(3^{{25}}$

$*3^{{25}}$

第三部分第三部分，共三部分：中国剩余定理测试

1选择两个数字。其中一个数字不是素数，第二个数字是需要测试素数的数字。“Prime1”=35Prime2=97

Image titled Check if a Number Is Prime Step 9

2分别选择两个大于零且小于prime1和prime2的数据点。他们不能互相平等。数据1=1数据2=2

Image titled Check if a Number Is Prime Step 10

3为素数1和素数计算MMI（数学乘法逆）：MMI=（素数2^（素数1-2））%PRIMEMI2=（素数1^（素数2-2））%2E。gMMI1=（97^33）%35MMI2=（35^95）%97

Image titled Check if a Number Is Prime Step 11

4为每个MMI创建一个二进制表，直到模块的Log2。对于MMI1F（1）=Prime2%Prime1=97%35=27F（2）=F（1）*F（1）%Prime1=27*27%35=29F（4）=F（2）*F（2）%Prime1=29*29%35=1F（8）=F（4）*F（4）%Prime1=1*1%35=1F（16）=F（8）*Prime1的二进制数-235-2=33（10001）基数2MMI1=F（33）=F（32）*F（1）mod 35MMI1=F（33）=1*27 mod 35MMI1=27mmi2f（1）=Prime1%Prime2=35%97=35F（2）=F（1）*F（1）%Prime2=35*35 mod 97=61F（4）=F（2）*F（2）%Prime2=61*61 mod 97=35F（8）=mod 97=35F（32）=F（16）*F（16）%Prime2=35*35 mod 97=61F（64）=F（32）*F（32）%Prime2=61*61 mod 97=35F（128）=F（64）*F（64）%Prime2=35*35 mod 97=61计算Prime2的二进制数-297-2=95=（1011111）基数2mi2=（（（（（F（64）*F（16）%97）*F（8）*F（4）%97）*97）*35%97）*61%97）*35%97）MMI2=61。

Image titled Check if a Number Is Prime Step 12

5计算（Data1*Prime2*MMI1+Data2*Prime1*MMI2）%（Prime1*Prime2）答案=（1*97*27+2*35*61）%（97*35）答案=（2619+4270）%3395答案=99

Image titled Check if a Number Is Prime Step 13

6验证“Prime1”不是PrimeCalculate（答案-数据1）%Prime199-1%35=28因为28大于0，35不是prime

Image titled Check if a Number Is Prime Step 14

7检查Prime2是否为PrimeCalculate（答案-数据2）%Prime299-2%97=0因为0等于0，97可能为prime

Image titled Check if a Number Is Prime Step 15

8至少再重复步骤1至7两次。如果步骤7为0：使用不同的“素数1”，其中素数1为非素数。使用不同的素数1，其中素数1为实际素数。在这种情况下，步骤6和7应等于0。对数据1和数据2使用不同的数据点。如果第7步每次都是0，那么prime2是prime的概率非常高。已知在某些情况下，当第一个数字是非素数，第二个素数是非素数“prime1”的一个因子时，步骤1到7会失败。它适用于两个数字都是素数的所有情况。重复第1步到第7步的原因是，在一些情况下，即使prime1不是质数，prime2不是质数，对于一个或两个数字，第7步仍然是零。这种情况很少见。通过将素数1改为不同的非素数，如果素数2不是素数，则在步骤7中，素数2将很快不等于零。除了“prime1”是prime2的一个因子的情况外，在步骤7中，素数总是等于零。。

Image titled Check if a Number Is Prime Step 16

1000以下的168个素数是：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、101、103、107、109、113、127、131、137、139、149、151、157、163、167、173、179、181、191、197、199、211、223、227、229、233、239、241、251、257、263、269、271、277、281、283、283、331、317、317、， 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
虽然对于大数字来说，试验分割比更复杂的方法慢，但对于小数字来说，它仍然相当有效。即使对于大数的素性测试，在没有发现小因素时，在切换到更高级的方法之前，先检查小因素也不少见。

发表于 2022-03-14 03:53
阅读 ( 113 )
分类：教育

你可能感兴趣的文章

什么是递归？如何使用它？

...，其中搜索结果建议是递归的。另一方面，如果您想学习如何编写递归函数，请继续阅读！ ...

发布于 2021-03-29 05:32
阅读 ( 237 )

python regex初出茅庐的程序员备忘单

...式作为根据您的首选名称自定义表达式作为pd导入在里面检查变量中是否存在值x=[1，4，6，7]如果x中有5:print（“有一个5”），否则：print（“没有5”）输出：没有5是检查两个变量是否引用一个元素x=[1，4，6，7]x=b打印（x是b）真...

发布于 2021-03-29 18:37
阅读 ( 258 )

...答网站分组。问题超级用户读者Franck Dernoncourt想知道如何在不自动更新自身的情况下检查Google Chrome的版本： I know that Google Chrome’s version information can be checked by going to chrome://help. However, if Google Chrome is not up to date, it will automati...

发布于 2021-04-09 03:41
阅读 ( 179 )

如何使bash提示符在登录到服务器时更改颜色？

...驱动的问答网站分组。问题超级用户读者nitins想知道如何使Bash提示符在登录到服务器时更改颜色： Is there a way to make the Bash Prompt dynamic so that it changes color when I am logged into a server? I want the color to be green when using my own personal syste...

发布于 2021-04-09 06:06
阅读 ( 229 )

硬盘上的数据会在没有损坏警告的情况下降级吗？

...天的问答环节是由SuperUser提供的，SuperUser是Stack Exchange的一个分支，是一个由社区驱动的问答网站分组。图片由通用公司（Flickr）提供。问题超级用户阅读器topo morto想知道硬盘上的数据是否可以降级，是否可以在没有损坏警...

发布于 2021-04-09 15:31
阅读 ( 280 )

如何使用powershell生成随机姓名和电话号码

...使用表示实际人员的真实数据。在这里，我们将带您了解如何使用PowerShell为此类场合生成随机姓名和电话号码列表。你需要什么在开始之前，您应该掌握一些工具和信息：动力壳此脚本是使用PowerShell 4.0开发的，并已测试与...

发布于 2021-04-11 08:59
阅读 ( 279 )

如何在不打开机箱的情况下检查计算机的ram配置？

...开案例的情况下找到您需要知道的所有信息。阅读以了解如何检查配置和安装的RAM模块统计信息。今天的问答环节是由SuperUser提供的，SuperUser是Stack Exchange的一个分支，是一个由社区驱动的问答网站分组。问题超级用户读者...

发布于 2021-04-11 14:32
阅读 ( 155 )

windows如何确认wi-fi访问以及是否需要热点身份验证？

...是用户体验中最理所当然的元素也有其内在机制。Windows如何告诉我们是否有internet连接以及是否需要登录Wi-Fi验证门户？答案超级用户贡献者Tobias Plutat提供了对流程的一些见解： After some digging (the sheer number of network and Internet re...

发布于 2021-04-12 03:47
阅读 ( 218 )