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


当前回答

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

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

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的质数,人们首先会期望一个循环,如下所示:

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

上面的循环是这样做的:对于给定的1 < i < n,它检查n/i是否为整数(余数为0)。如果存在一个i,其中n/i是整数,那么我们可以确定n不是质数,此时循环终止。如果没有i, n/i是整数,那么n是素数。

和每一个算法一样,我们会问:我们能做得更好吗?

让我们看看上面的循环中发生了什么。

i的序列是:i = 2,3,4,…, n - 1

整数检查的顺序是:j = n/i,也就是n/2, n/3, n/4,…n (n - 1) /

如果对于某些i = a, n/a是一个整数,那么n/a = k(整数)

或者n = ak,显然是n > k > 1(如果k = 1,那么a = n,但我从来没有达到n;如果k = n,那么a = 1,但我从2开始

同样,n/k = a,如上所述,a是i的值,所以n > a > 1。

所以,a和k都是1和n之间的整数(排他)。由于i达到了该范围内的每一个整数,在某个迭代i = a时,在另一个迭代i = k时。如果n的质数检验对于min(a,k)失败,那么对于max(a,k)也会失败。所以我们只需要检查这两种情况中的一种,除非min(a,k) = max(a,k)(其中两次检查减少为一次),即a = k,此时a*a = n,这意味着a =根号(n)。

换句话说,如果n的质数检验对于某些i >=√(n)(即max(a,k))失败,那么对于某些i <= n(即min(a,k))也会失败。因此,如果我们运行i = 2到根号n的测试就足够了。

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

n = a * b

现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,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)总是正确的。

假设我们有一个数字“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不是一个质数(大于1),那么有数字a和b满足

n = ab      (1 < a <= b < n)

通过将a<=b的关系乘以a和b,我们得到:

a^2 <= ab
 ab <= b^2

因此:(注意n=ab)

a^2 <= n <= b^2

因此:(注意a和b是正的)

a <= sqrt(n) <= b

因此,如果一个数(大于1)不是质数,并且我们测试到该数的平方根的可除性,我们将找到其中一个因数。