Question

c++上的判断一个整数是否是素数，那个什么平方根的搞不懂，谁解释一下

Answer 1

观察：
4=2×2
6=2×3
12=2×6=3×4
若n是合数，则n一定能分解成两个整数之积，不妨设n=a×b 且a≤b，则易知 a≤√n，
也就是说：若n是合数，则在2~√n之间至少有一个因数，否则n就是素数。

Answer 2

判断n是不是素数就是看有没有x*y=n;
x可为2至n-1的数；
但当x<=y没有x*y=n;就没有了；
所以x只需取2至y最小值即可；
因为x*y=n>x*x;所以x最大为根号n；
即只需检索2到根号n即可；

Answer 3

信息安全数学基础上有详细的证明