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


当前回答

假设我们有一个数字“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的另一个因子必然小于根号n。

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

n = a * b

现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在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”。

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

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

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

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;
}