要测试一个数是否是素数还是不为什么我们还要测试它是否是唯一的整除高达这个数字的平方根？

To test whether a number is prime or not why do we have to test whether it is divisible only upto the square root of that number ?

推荐答案

如果一个数 N 不是素，它可以分解成两个因素 A 和 B ：

If a number n is not a prime, it can be factored into two factors a and b:

n = a*b

如果两个 A 和 B 均大于平方根 N ， A * B 将大于 N 。因此，这些因素至少有一个必须小于或等于平方根 N ，并检查 N 是素数，我们只需要测试因子小于或等于平方根

If both a and b were greater than the square root of n, a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.