隐约记得之前做过一个c++的题目是判断一个数是否素数（质数） 我当时给的算法是判断 2 - x/2, 因为被除数大于 x/2 那商一定小于2，所以被除数必须大于x/2

最近看书的时候发现通用的算法是计算 2- sqrt(x) 即 根号x 这就让我产生疑问了，毋庸置疑，这个算法的效率更高，时间复杂度是logn。 那为什么到sqrt(x)就够了呢？

我反复思考总算得出了结论，这里用反证法即可：

已知 n 不是素数，且a，b是 n的两个根， a*b = n
假设 b>sqrt(n)，且a>=sqrt(n)
则a*b > sqrt(n) * sqrt(n) 即 a*b > n 与条件相悖

得出若存在一个根大于sqrt(n)，
那必定存在另一个小于sqrt(n)的根

与此对应的逆否命题是

若不存在小于sqrt(n)的根，则不存在大于sqrt(n)的根

根据这个证明的结论，判断是否是素数，最多只需要判断到 n 的平方根即可。