要检验一个数是不是质数,为什么我们要检验它是否只能被这个数的平方根整除?


当前回答

为了检验一个数N是不是质数。 我们只需要检查N是否能被<=SQROOT(N)的数整除。这是因为,如果我们把N分解成任意两个因子比如X和Y。N = XY。 X和Y都不能小于SQROOT(N)因为XY < N X和Y都不能大于SQROOT(N)因为X*Y >n

因此,一个因子必须小于或等于SQROOT(N)(而另一个因子大于或等于SQROOT(N))。 因此,要检查N是否为质数,我们只需要检查那些<= SQROOT(N)的数字。

其他回答

其实就是基本的因式分解和平方根。

它可能看起来很抽象,但实际上它只是在于这样一个事实,即一个非质数的最大可能阶乘必须是它的平方根,因为:

sqrroot(n) * sqrroot(n) = n。

鉴于此,如果任何大于1且小于或大于√(n)的整数能被n整除,则n不可能是质数。

伪代码示例:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

如果一个数n不是质数,它可以被分解成两个因子a和b:

n = a * b

现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。

设n是非素数。因此,它至少有两个大于1的整数因子。设f是n个这样的因子中最小的。设f >√n,则n/f是一个≤√n的整数,因此小于f,因此f不可能是n的最小因子。反证法;N的最小因子必须≤根号N。

假设给定的整数N不是质数,

则N可分解为a和b两个因子,2 <= a, b < N使N = a*b。 显然,它们不能同时大于根号N。

让我们不失一般性地假设a更小。

现在,如果你找不到N的任何除数在[2,根号(N)]范围内,这意味着什么?

这意味着当N <=√(N)时,N在[2,a]中没有任何除数。

因此,a = 1且b = n,因此根据定义,n是素数。

...

如果您不满意,请继续阅读:

(a, b)可能有许多不同的组合。假设它们是:

(a1, b1), (a2, b2), (a3, b3), ....., (ak, bk)。在不失一般性的前提下,假设ai < bi, 1<= i <=k。

现在,为了证明N不是质数它足以证明ai都不能被进一步分解。我们还知道ai <=根号N,因此你需要检查根号N,这将涵盖所有ai。这样你就能得出N是不是质数。

...

因为如果一个因子大于根号n,那么与它相乘等于n的另一个因子必然小于根号n。