第五步中的i＞n－1什么意思，i不是表示2到n－1的任意整数吗，为什么会有i＞n－1？第五步中的n－1是什么意思

更新时间2019-02-28 15:55:21

？i又是什么意思？

1、i 是怎样从 2 到 n - 1 的？注意第四步，每做一次除法，i 就增大 1;

如果不加限制，i 会一直增大，以致比 n 还大 。但显然不需要 i > n-1，所以需要第五步，i 每次加1后，都要判断 i 是否大于 n -1，大于了，就终止计算 。

2、i > n-1，就是 i = n，完全可以写作 i = n，不必拘泥于教材的写法。

3、更重要的是，i 不必增加到 n 或 n - 1，只要 i > √n，就可以终止计算了。

因为合数的因数是成对的，n 有一个因数 a，则 n/a = b，即势必有一个因数 b；

设开始时 a < b；a 逐渐增大时，b 就逐渐减小；当 a = √n，b = √n，两数相等；此后 a > b，a 相当于之前的 b，b 相当于之前的 a ;

所以，若从 2 到 √n 都找不到 a，就没必要让 a 继续增大。因为如果在 √n 到 n 中能找到因数 a，则势必在 √n 到 2 中存在因数 b，而这是不可能的，a 已经试过这个范围了。 

例如，√145 = 12.04，判断 145 是否质数，只要试除以 2 ~ 11 就可以了，比如它有因数29，大于12，但145/29 = 5，之前试到 5，就已经得到结果了 。

当 n 很大时，类似这样的算法优化是很有意义的。试想有一个接近一百万的质数，若 i 从 2 变到 n，要做将近一百万次除法，才能判断出 n 是质数。而 √1000000 = 1000，i 从 2 到 1000，只需要做1000次除法，就已经得到结果。计算量仅为前者的千分之一 。