本文介绍了为什么我们只检查素数的平方根来确定它是否是素数?我们不能用立方根吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
如果一个数 n 可以写成 axb 并且 m=sqrt(n).这里n=m*m.我们说我们只需要检查 m,因为 min(a,b)<=m.所以我们不能取立方根吗?假设我们取 n=21,那么 n=1x3x7.但是Cube root是2,为什么这个方法会失败?
If a number n can be written as axb and m=sqrt(n). Here n=m*m. We say we only need to check upto m because min(a,b)<=m. So cant we take cube roots? Suppose we take n=21, then n=1x3x7. But Cube root is 2. Why does this method fail?
推荐答案考虑 n = 143 = 11 * 13.143 的立方根在 5 到 6 之间.如果你只测试整除性到 6 的质数,你将找不到 n 的两个因数中的任何一个,并且会错误地得出 143 是质数.
Consider n = 143 = 11 * 13. The cube root of 143 is between 5 and 6. If you only test divisibility by the primes up to 6, you will not find either of the two factors of n and will mistakenly conclude that 143 is prime.
更多推荐
为什么我们只检查素数的平方根来确定它是否是素数?我们不能用立方根吗?
发布评论