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


当前回答

对于任意数n,求因数的一种方法是求根号p:

sqrt(n) = p

当然,如果我们用p乘以它自己,就会得到n:

p*p = n

可以改写为:

a*b = n

其中p = a = b,如果a增加,则b减少,以保持a*b = n,因此p为上限。

Update: I am re-reading this answer again today and it became clearer to me more. The value p does not necessarily mean an integer because if it is, then n would not be a prime. So, p could be a real number (ie, with fractions). And instead of going through the whole range of n, now we only need to go through the whole range of p. The other p is a mirror copy so in effect we halve the range. And then, now I am seeing that we can actually continue re-doing the square root and doing it to p to further half the range.

其他回答

是的,正如上面所解释的,迭代到Math就足够了。对一个数的平方根取底,以检查其质数(因为SQRT涵盖了所有可能的除法情况;和数学。因为任何高于SQRT的整数已经超出了它的范围)。

下面是一个可运行的JavaScript代码片段,它代表了这种方法的简单实现-它的“运行时友好性”足以处理相当大的数字(我试着检查质数和非质数,最大可达10**12,即1万亿,将结果与在线质数数据库进行比较,即使在我的廉价手机上也没有遇到错误或延迟):

function isPrime(num) { if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) { return num === 2; } else { const sqrt = Math.floor(Math.sqrt(num)); for (let i = 3; i <= sqrt; i += 2) { if (num % i === 0) return false; } return true; } } <label for="inp">Enter a number and click "Check!":</label><br> <input type="number" id="inp"></input> <button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

任何合数都是质数的乘积。

假设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)总是正确的。

假设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)不是质数,并且我们测试到该数的平方根的可除性,我们将找到其中一个因数。

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

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的测试就足够了。