要检验一个数是不是质数,为什么我们要检验它是否只能被这个数的平方根整除?
当前回答
因为如果一个因子大于根号n,那么与它相乘等于n的另一个因子必然小于根号n。
其他回答
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,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是否能被<=SQROOT(N)的数整除。这是因为,如果我们把N分解成任意两个因子比如X和Y。N = XY。 X和Y都不能小于SQROOT(N)因为XY < N X和Y都不能大于SQROOT(N)因为X*Y >n
因此,一个因子必须小于或等于SQROOT(N)(而另一个因子大于或等于SQROOT(N))。 因此,要检查N是否为质数,我们只需要检查那些<= SQROOT(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,那么与它相乘等于n的另一个因子必然小于根号n。
推荐文章
- 如何用动态规划确定最长递增子序列?
- 在c++程序中以编程方式检测字节序
- 理解递归
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 给定一个数字,找出下一个与原始数字具有完全相同的数字集的更高的数字
- HSL到RGB的颜色转换
- 使用Java在原语数组中查找最大/最小值
- 好的Java图算法库?
- 什么时候我应该使用Kruskal而不是Prim(反之亦然)?
- 取一个集中在中心的随机数
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下,您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何使用JavaScript比较软件版本号?数量(只)