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

Question

为什么我们检查一个素数的平方根来确定它是否是素数？要检验一个数字是否素数，为什么我们要测试它是否只能被除以到这个数的平方根呢？

Answer 1

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

n = a * b

如果两者都是a和b的平方根大于n，然后a * b会比n..因此，这些因子中至少有一个必须小于或等于n，如果我们找不到任何小于或等于平方根的因素，n一定是一流的。

Answer 2

一个更直观的解释是：-

100的平方根是10，假设a，b=100，对于不同对的a和b。

如果a=b，那么它们是相等的，并且是100的平方根。也就是10。

如果其中一个小于10，另一个必须更大。例如，5x20=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但小于或等于平方根的每一个素数。