为什么我们只检查素数的平方根来确定它是否是素数?我们不能用立方根吗? [英] Why do we only check up to the square root of a prime number to determine if it is prime? Can't we use cube root?

问题描述

如果一个数 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.

这篇关于为什么我们只检查素数的平方根来确定它是否是素数?我们不能用立方根吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！