为了检验一个数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)的数字。

假设给定的整数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是不是质数。

...

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

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

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

是的，正如上面所解释的，迭代到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不是一个质数(大于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)不是质数，并且我们测试到该数的平方根的可除性，我们将找到其中一个因数。