为了测试一个数字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不是质数，

则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，求因数的一种方法是求根号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，那么与它相乘等于n的另一个因子必然小于根号n。

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

n = a * b

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