当前位置：新励学网 > 秒知问答 > 找质数的方法

找质数的方法

发表时间：2024-07-31 10:12:34 来源：网友投稿

方法一：要想知道x是不是质数，那就用它试着去除2~x-1，如果可以被整除，那就不是质数呗。

毫无疑问这个算法效率是低到人难以忍受的。稍微优化一下，我们可以得到方法二。步骤/方式二方法二：第一个质数为2，那x只要是大于2的偶数就必然不是质数，这样我们就能排除掉一半的数了。对于奇数x，用它试着去除3、5...~x-2，如果可以被整除，那就不是质数。计算效率高了一些，但算法复杂度本质上和第一种没什么区别，只是系数级的改进。步骤/方式三方法三：稍微思考一下就会发现，其实质数是分解质因数时只能分解成1和本身的数，既然如此，那么我们在试除的时候就没有必要从3、5一直除到x-2了，只需要除比自身小的质数就可以了。步骤/方式四方法四：再进一步思考就会发现，其实也没必要去试除所有比自身小的质数，只要试除比不大于自身的平方根的质数就可以了。为什么？假设x不是质数，那么它必然是最少两个质数的乘积，如果这两个质因数不相等，那么必然有一个质因数小于√x，如果两个质因数相等，那么这个质因数必然等于√x。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！