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

对于任意数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.

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

是的，正如上面所解释的，迭代到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不是质数，它可以被分解成两个因子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不是质数。