请高手解释下这段代码的算法!!

Question

这个方式是检查一个数是不是质数的
private boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
                return true;
}
参数n为任意一个整数,检查这个数是否为质数i = 2: 是从2开始,因为质数可以被1整除
n % i == 0: return false,是说整除为0就不是整数,返回最不理解的是那循环条件,为什么可以这样写 i*i <= n请各位解释下,我很菜....

Answer 1

按照你上面的代码的意思应该就是：用2到根号N之间的所有整数去除N就可以证明N是否为素数)：
具体描述一下：假设 N 从2到根号N都没有它的因数，而他有一个因数是m并且是大于根号N，很显然有：N/m = n（一个整数），由于m>根号N，n<根号N 这说明N从2到根号N有它的因数，与假设相反（即返回false）
ps~~你上面提到的“ i*i <= n ”，其实就是求出根号N的值，写法不同而已！
再PS~~素数的准确公式到目前仍在研究中，目前数学家也没有最准确的算法，只是近似的。。
希望对你有帮助！

Answer 2

LZ你这样思考下,如果你要判断一个数int n是不是质数,如果从2一直判断到了n的平方根的话.是不是正好判断完.?
  如果再判断n的平方根后面的数  循环就重复了.. 例如说
  你判断20是不是质数,  20的平方根大约是2*2.236的话,循环从i=2开始,,判断2.3.4的情况,再往上判断的话就多余了阿, 到6=2*3,8=2*4,  其实我也不太明白这里面是怎么处理的..只是当时上学的时候学的一个什么定理..当定理记住了.呵呵

Answer 3

谢谢你的分析,我差不多懂了,
private boolean isPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0)
return false;
}
return true;
}
可以写出这样的,打个比方,n为20 平方根的整数为4只要循环到4就可以了,因为循环到8,12是在做无用功,8,12是4的倍数

Answer 4

从2到N的平方根是i的取值范围。
如果一个数能表示成a*b
则一定有a<=sqrt（a*b)||b<=sqrt(a*b)成立