c – 查找素数？
发布时间：2020-12-16 05:51:05 所属栏目：百科 来源：网络整理
导读：要查找N是否是素数,我们只需要查找小于或等于sqrt(N)的所有数字.这是为什么？我正在编写一个C代码,以便理解背后的原因. 解决方法 N是素数,如果它是一个正整数,它可以被两个正整数1和N整除.由于一个数除数不能大于该数,所以产生一个简单的原语测试： 如果大于
|
要查找N是否是素数,我们只需要查找小于或等于sqrt(N)的所有数字.这是为什么？我正在编写一个C代码,以便理解背后的原因.
解决方法
N是素数,如果它是一个正整数,它可以被两个正整数1和N整除.由于一个数除数不能大于该数,所以产生一个简单的原语测试：
>如果大于1的整数N不能被范围[2,N-1]中的任何整数整除,则N是素数.否则,N不是素数. 但是,修改此测试以使其更快速度将是非常好的.所以让我们进行调查. 请注意,N的除数成对出现.如果N可以被M除数,那么也可以被N / M整除.例如,12被6除以,并且也是2.而且,如果M> = sqrt(N),那么N / M <= sqrt(N). 这意味着如果小于或等于sqrt(N)的数除以N,则没有大于sqrt(N)的数除N(除了1和N本身之外),否则会出现矛盾. 所以我们有一个更好的测试： 如果您考虑上述推理,您应该看到通过此测试的一个数字也会通过第一个测试,而该测试失败的数字也将在第一次测试中失败.因此,测试是相当的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |