为了测试一个数字是否为素数，为什么我们必须测试它是否只能被该数字的平方根整除？
如果一个数字n不是素数，它可以被考虑到两个因素a和b：
n = a * b
如果a和b都大于n的平方根，那么a * b将大于n。因此，这些因素中至少有一个必须小于或等于n的平方根，如果我们找不到任何小于或等于平方根的因子，n必须是素数。
设n为非素数。因此，它至少有两个大于1的整数因子。令f是n个这样的因子中最小的。假设f> sqrt n。那么n / f是整数LTE sqrt n，因此小于f。因此，f不能是n的最小因子。 Reductio ad absurdum; n的最小因子必须是LTE sqrt n。
鉴于任何数字n，那么找到其因素的一种方法是得到它的平方根p：
sqrt(n) = p
当然，如果我们自己乘以p，那么我们回到n：
p*p = n
它可以重写为：
a*b = n
哪里p = a = b。如果a增加，那么b减少以维持a*b = n。因此，p是上限。
为了测试数字的素数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不是素数，此时循环终止。如果对于no 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 = a，并且在某个其他迭代i = k。如果n的素数测试对于min（a，k）失败，则对于max（a，k）也将失败。所以我们只需要检查这两种情况中的一种，除非min（a，k）= max（a，k）（其中两个检查减少到一个），即a = k，此时a * a = n，暗示a = sqrt（n）。
换句话说，如果对于某些i> = sqrt（n）（即，max（a，k）），n的素性测试失败，那么对于某些i <= n（即min（a），它也会失败中，k））。因此，如果我们运行i = 2到sqrt（n）的测试就足够了。
任何复合数都是素数的乘积。
让我们说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)总是如此。
让我们说m = sqrt(n)然后m × m = n。现在如果n不是素数那么n可以写成n = a × b，所以m × m = a × b。请注意，m是一个实数，而n，a和b是自然数。
现在可以有3种情况：
在所有3例中，min(a, b) ≤ m。因此，如果我们搜索到m，我们必然会找到至少一个n因子，这足以证明n不是素数。
因为如果一个因子大于n的平方根，那么与它相乘的另一个因子等于n必然小于n的平方根。
更直观的解释是： -
对于a和b的各种对，100的平方根是10.假设x b = 100。
如果a == b，那么它们是相等的，并且是100的平方根。这是10。
如果其中一个小于10，则另一个必须更大。例如，5 x 20 == 100.一个大于10，另一个小于10。
考虑到x b，如果其中一个出现故障，另一个必须变得更大以进行补偿，因此产品保持在100.它们围绕平方根旋转。
101的平方根约为10.049875621。因此，如果你要测试数字101的素数，你只需要尝试直到10的整数，包括10.但是8,9和10本身不是素数，所以你只需要测试7，这是主要。
因为如果存在一对具有大于10的数字的因子，则该对中的另一个必须小于10.如果较小的一个不存在，则没有匹配的较大因子101。
如果您正在测试121，则平方根为11.您必须测试1到11（包括）的素数整数，以查看它是否均匀进入。 11进11次，所以121不是素数。如果你已经停在10点，而没有经过测试11，你就错过了11点。
假设您只测试奇数，则必须测试大于2但小于或等于平方根的每个素数。
`
假设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）不是素数，并且我们测试可达性达到数字的平方根，我们将找到其中一个因素。
这些只是分解和平方根的基本用法。
它可能看起来是抽象的，但实际上它只是因为非素数的最大可能因子必须是它的平方根，因为：
sqrroot(n) * sqrroot(n) = n。
鉴于此，如果任何高于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不是素数，
那么N可以分解成两个因子a和b，2 <= a, b < N这样的N = a*b。显然，它们都不能同时大于sqrt(N)。
让我们假设a较小而不失一般性。
现在，如果你找不到属于N范围的[2, sqrt(N)]的任何除数，那是什么意思？
这意味着N在[2, a]中没有任何除数作为a <= sqrt(N)。
因此，a = 1和b = n因此根据定义，N是素数。
...
如果您不满意，请进一步阅读：
(a, b)的许多不同组合都是可能的。让我们说它们是：
（a1，b1），（a2，b2），（a3，b3），.....，（ak，bk）。不失一般性，假设ai <bi，1<= i <=k。
现在，为了能够证明N不是素数，足以表明没有ai可以进一步分解。而且我们也知道ai <= sqrt(N)因此你需要检查直到sqrt(N)将覆盖所有ai。因此，你将能够得出结论N是否是素数。
...
所以检查数字N是否为Prime。我们只需要检查N是否可被数字<= SQROOT（N）整除。这是因为，如果我们将N分解为任何2个因子，比如X和Y，即。 N = XY。 X和Y中的每一个都不能小于SQROOT（N），因为那时，XY <N X和Y中的每一个都不能大于SQROOT（N），因为那时，X * Y> N
因此，一个因子必须小于或等于SQROOT（N）（而另一个因子大于或等于SQROOT（N））。因此，要检查N是否为Prime，我们只需检查那些数字<= SQROOT（N）。
假设我们有一个数字“a”，它不是素数[不是素数/复合数字意味着 - 一个数字，可以用1或其自身以外的数字均分。例如，6可以均匀地分为2或3，以及1或6]。
6 = 1×6或6 = 2×3
所以现在如果“a”不是素数那么它可以除以另外两个数字，让我们说这些数字是“b”和“c”。意思是
α= B * C。
现在，如果“b”或“c”，它们中的任何一个都大于“a”的平方根，而“b”和“c”的乘法将大于“a”。
因此，“b”和“c”总是<=“a”的平方根，以证明方程“a = b * c”。
由于上述原因，当我们测试一个数字是否为素数时，我们只检查该数字的平方根。