要查找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本身之外),否则会出现矛盾. 所以我们有一个更好的测试：
>如果大于1的整数N不能被[2,sqrt(N)]范围内的任何整数整除,N不是素数.
如果您考虑上述推理,您应该看到通过此测试的一个数字也会通过第一个测试,而该测试失败的数字也将在第一次测试中失败.因此,测试是相当的.
