查找素数？

Question

为了找出N是素数,我们只需要查找小于或等于sqrt(N)的所有数.这是为什么？我正在编写一个C代码,试图理解它背后的原因.

Answer 1

N是素数,如果它是一个正整数,它可以被正整数两个正整数1和N整除.由于数的除数不能大于这个数,这就产生了一个简单的素数测试:

• 如果整数N(大于1)不能被该范围内的任何整数整除[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本身),否则会产生矛盾.

所以我们有一个更好的测试:

• 如果整数N(大于1)不能被该范围内的任何整数整除[2, sqrt(N)],则N为素数.否则,N不是素数.

如果你考虑上面的推理,你应该看到通过这个测试的数字也通过了第一次测试,并且未通过这个测试的数字也没有通过第一次测试.因此测试是等效的.

Answer 2

一个复合数(一个非素数,或1)至少有一对因子,并且保证每对中的一个数字小于或等于数字的平方根(这就是你正在询问).

如果你对数字的平方根进行平方,你得到数字本身(sqrt(n) * sqrt(n) = n),所以如果你把一个数字做得更大(比sqrt(n)),那么你必须让另一个更小.如果您只检查数字2,sqrt(n)您将检查所有可能的因素,因为每个因素将与一个大于的数字配对sqrt(n)(当然,如果该数字实际上是某个其他数字的正方形) ,如4,9,16等......但这并不重要,因为你知道它们不是素数;它们很容易被sqrt(n)自己考虑在内).

Answer 3

原因很简单,任何大于sqrt的数字都会导致另一个乘数小于sqrt.在这种情况下,您应该已经检查过它.