为什么我们要检查一个数的平方根来确定它是否是质数?

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

n = a * b

现在a和b不可能都大于n的平方根，因为这样乘积a * b就会大于sqrt(n) * sqrt(n) = n。因此，在对n的任何因式分解中，至少有一个因子必须小于n的平方根，如果我们找不到任何小于或等于平方根的因子，n一定是质数。

因为如果一个因子大于根号n，那么与它相乘等于n的另一个因子必然小于根号n。

比方说m = sqrt(n)，然后是m × m = n。现在如果n不是质数，那么n可以写成n = a × b，所以是m × m = a × b。注意，m是实数，而n、a和b是自然数。

现在有三种情况:

1. A > m⇒b <米
2. ⇒A = m, b = m
3. & lt;⇒⇒M

在这三种情况下，都是min(a, b) ≤ m。因此，如果我们搜索到m，我们一定会找到n的至少一个因数，这足以表明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)不是质数，并且我们测试到该数的平方根的可除性，我们将找到其中一个因数。

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

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

# EYZ1。

据此，如果任何高于1、低于或高于sqrroot(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/f是一个≤根号n的整数，因此小于f，因此f不可能是n的最小因子。反证法;N的最小因子必须≤根号N。

所以要检查一个数字N是不是质数。 我们只需要检查N是否能被numbers<=SQROOT(N)整除。这是因为，如果我们把N分解成任意两个因子比如X和Y。N = X < em > Y。 X和Y都不能小于SQROOT(N)，因为XY <N X和Y都不能大于SQROOT(N)，因为X*Y > N

因此其中一个因子必须小于或等于SQROOT(N)(而另一个因子大于或等于SQROOT(N))。 因此，要检查N是否为质数，我们只需检查这些数字<= SQROOT(N).

为了测试数字n的质数，首先应该执行如下循环:

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

上面的循环是这样做的:对于给定的1 & lt;我& lt;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 >= sqrt(n)(即max(a,k))失败，那么对于某些i <= n(即min(a,k))也会失败。因此，如果我们运行i = 2到根号n的测试就足够了。

假设给定的整数N不是质数，

让我们在不失一般性的前提下假设a更小。

现在，如果在[2, sqrt(N)]范围内找不到N的任何除数，这意味着什么?

这意味着N在[2, a]和a <= sqrt(N)中没有任何除数。

因此，a = 1和b = n，因此是根据定义，N是质数。

.．.

如果您不满意，请继续阅读:

(a, b)可能有许多不同的组合。假设它们是:

(# EYZ1, b # EYZ1), (# EYZ3, b # EYZ3), (# EYZ5, b # EYZ5),…(a_k, b_k)。在不失一般性的前提下，假设一个_我 <b # EYZ9 # EYZ0。

现在，为了证明N不是质数，只要证明_我中的任何一个都不能被进一步分解就足够了。我们还知道_我 <= sqrt(N)，因此你需要检查到sqrt(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”。

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

对于任意数字n，求其因式的一种方法是求其平方根p:

sqrt(n) = p

当然，如果我们将p与自身相乘，那么我们就会得到n:

p*p = n

可以改写为:

a*b = n

# EYZ0的地方。如果a增加，那么b减少以保持a*b = n。因此，p是上限。

今天我又重读了一遍这个答案，对我来说更清楚了。值p并不一定意味着整数，因为如果它是整数，那么n就不是质数。因此，p可以是一个实数(即，带分数)。不用遍历n的整个范围，现在我们只需要遍历p的整个范围。另一个p是镜像副本，所以我们将范围减半。然后，现在我看到我们实际上可以继续重新做square root，并将其做到p，以进一步扩大一半的范围。

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

比方说n = p1 * p2，其中p2 > p1和它们都是质数。

如果n % p1 === 0，则n是一个合数。

如果n % p2 === 0，那么猜猜n % p1 === 0 !

所以没有办法同时使用n % p2 === 0和n % p1 !== 0。 换句话说，如果一个合数n可以被 p2、p3…π(它的较大因子)也必须除以它的最小因子p1。 事实证明，最低因子p1 <= Math.square(n)总是正确的

是的，正如上面所解释的，迭代到Math就足够了。(因为sqrt涵盖了所有可能的除法情况;和Math.floor，因为任何高于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>