algorithm - 为什么我们要检查一个数的平方根以确定该数是否为质数？

Question

要测试一个数是否为质数，为什么我们必须测试它是否只能被该数的平方根整除？

Answer 1

如果一个数 n 不是素数，它可以分解为两个因子 a 和 b:

n = a * b

现在 a 和 b 不能都大于 n 的平方根，从那时起 a * b 将大于 sqrt(n) * sqrt(n) = n。所以在 n 的任何因式分解中，至少有一个因子必须小于 n 的平方根，如果我们找不到任何小于或等于的因子求平方根，n 必须是素数。