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


当前回答

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

其他回答

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

假设m =根号n,那么m × m = n。如果n不是质数,那么n可以写成n = a × b,所以m × m = a × b。注意,m是实数,而n、a和b是自然数。

现在有三种情况:

A > m⇒b < m ⇒A = m, b = m A < m⇒b > m

在这三种情况下,min(a, b)≤m。因此,如果我们搜索到m,我们一定会找到n的至少一个因子,这足以证明n不是质数。

假设我们有一个数字“a”,它不是质数[非质数/合数的意思是-一个可以被除1或它本身以外的数字整除的数字。例如,6可以被2或3整除,也可以被1或6整除。

6 = 1 × 6或6 = 2 × 3

如果a不是质数那么它可以被另外两个数除我们设这两个数是b和c。这意味着

a = b * c。

现在如果b或c,它们中的任何一个大于a的平方根那么b和c的乘积就会大于a。

因此,“b”或“c”总是<=“a”的平方根来证明方程“a=b*c”。

由于上述原因,当我们测试一个数字是否是质数时,我们只检查到该数字的平方根。

假设给定的整数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 = p1 * p2,其中p2 > p1,它们都是质数。

如果n % p1 === 0,则n是一个合数。

如果n % p2 === 0,那么猜猜n % p1 === 0 !

因此,如果n % p2 === 0,同时n % p1 !== 0,这是不可能的。 换句话说,如果一个合数n能被 p2、p3……PI(较大因子)也要除以最小因子p1。 事实证明,最低因子p1 <= Math.square(n)总是正确的。