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

为了检验一个数是否为素数，为什么我们只能测试它是否可以整除到该数的平方根？

Answer 1

如果n不是素数，则可以将其分解为两个因素a和b ：

 n = a*b 

如果a和b都大于n平方根，则a*b将大于n 。 所以这些因素中至少有一个必须小于或等于n平方根，为了检查n是否是素数，我们只需要测试小于或等于平方根的因子。

Answer 2

假设m = sqrt(n)那么m × m = n 。 现在，如果n不是素数，那么n可以写成n = a × b ，所以m × m = a × b 。 注意m是一个实数，而n ， a和b是自然数。

现在可以有三种情况：

1. a> m⇒b <m
2. a = m⇒b = m
3. a <m⇒b> m

在所有3种情况下， min(a, b) ≤ m 。 因此，如果我们搜索到m ，我们一定会发现至少有一个n因子，这足以表明n不是素数。

Answer 3

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

Answer 4

更直观的解释是：

100的平方根是10.假设axb = 100，对于a和b的各种对。

如果a == b，则它们是相等的，并且是100的平方根。 这是10。

如果其中一个小于10，另一个必须更大。 例如，5 x 20 == 100.一个大于10，另一个小于10。

思考axb，如果其中一个倒下，另一个必须做大才能补偿，所以产品保持在100.它们绕着平方根旋转。

101的平方根约为10.049875621。 所以如果你测试素数为101的数字，你只需要尝试10到10的整数。但是8,9和10不是他们自己的素数，所以你只需要测试到7，这是主要。

因为如果有一对数大于10的数字之一，那么这一对中的另一个必须小于10.如果较小的一个不存在，则没有匹配的较大的因子101。

如果你正在测试121，那么平方根就是11.你必须测试1到11（包括1）的整数，看看它是否平均。 11次进11次，所以121次不是素数。 如果你已经停在10，而没有测试过11，那么你就错过了11。

假设您只测试奇数，您必须测试每个大于2的整数，但小于或等于平方根。

`

Answer 5

假设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）不是素数，而且我们测试的可分性达到数的平方根，我们会发现其中一个因素。

Answer 6

这只是分解和平方根的基本用法。

这看起来可能是抽象的，但事实上，它只是因为：非素数的最大可能因子必须是其平方根，因为：

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; } 

Answer 7

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

那么N可以因式分解成两个因子a和b ， 2 <= a, b < N使得N = a*b 。 显然，它们都不能同时大于sqrt(N) 。

让我们假设不失一般性， a更小。

现在，如果找不到范围[2, sqrt(N)]的N除数，那么这是什么意思？

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

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

…

进一步阅读，如果你不满意：

(a, b)许多不同的组合可能是可能的。 假设他们是：

（a ₁ ，b ₁ ），（a ₂ ，b ₂ ），（a ₃ ，b ₃ ），…，（a _k ，b _k ）。 不失一般性，假设_i <b _i ， 1<= i <=k 。

现在，要能够证明N不是素数，就足以证明_我没有一个可以进一步因式分解。 而且我们也知道一个_i <= sqrt(N) ，因此你需要检查直到sqrt(N) ，它将覆盖所有的_i 。 因此，你将能够得出N是否为素数的结论。

…

Answer 8

设n是非素数。 因此，它至少有两个大于1的整数因子。设f是n的这些因子中最小的。 假设f> sqrt n。 那么n / f是整数LTE sqrt n，因此小于f。 因此，f不能是n的最小因子。 减少和消除 n的最小因子必​​须是LTE sqrt n。

Answer 9

假设我们有一个数字“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”。

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

Answer 10

所以要检查一个数字N是不是Prime。 我们只需要检查N是否可以被数字<= SQROOT（N）整除。 这是因为，如果我们把N纳入任何2个因素中，就称X和Y，即。 N = X Y.因此，X和Y中的每一个不能小于SQROOT（N），因为那么 X和Y不能大于SQROOT（N），因为那么X * Y> N

因此，一个因子必须小于或等于SQROOT（N）（而另一个因子大于或等于SQROOT（N））。 所以要检查N是否是Prime，我们只需要检查那些数字<= SQROOT（N）。

Answer 11

为了检验一个数字的素数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不是素数，在这一点上循环终止。 如果没有我，n / i是一个整数，那么n是素数。

就像每个算法一样，我们问： 我们可以做得更好吗？

让我们看看上面的循环中发生了什么。

我的顺序是：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）。

换句话说，如果n的素性检验对某些i> = sqrt（n）（即max（a，k））失败了，那么对于某个i <= n也将失败（即min（a中，k））。 所以，如果我们对sqrt（n）运行i = 2的测试就足够了。