求质数的算法

比如，求10 000 000中有多少个质数

质数是只能被1和自己整除的自然数（不包括1）。

笨办法就是一个个计算，用到两层嵌套的循环，数字一大算死人，代码如下：

public class PrimeNumbers { public static void main(String[] args) { final int max = 100; int count = 0; boolean flag = true; for (int i = 2; i <= max; i++) { for (int j = 2; j < i; j++) { if (i % j == 0) { flag = false; break; } flag = true; } if (flag) { count++; } } System.out.println("质数数是：" + count); } }

运行时间，如果求100 000以内的质数，大概2800毫秒，决定每次运行程序时系统的软硬件情况，不过就是这个数量级，没有大的变化。

那么如果不是质数，这个数就是合数，合数的最小因数小于它的平方根。

好了，聪明一点的办法来了，时间大大节省。

public class PrimeNumbers { public static void main(String[] args) { final int max = 100; int count = 0; boolean flag = true; for (int i = 2; i <= max; i++) { for (int j = 2; j <= Math.sqrt(i); j++) { if (i % j == 0) { flag = false; break; } flag = true; } if (flag) { count++; } } System.out.println("质数数是：" + count); } }

运行时间，如果求100 000以内的质数，大概30毫秒，决定每次运行程序时系统的软硬件情况，没有大的变化。
两次运行时间相差两个数量级，算法重要吗，当然很重要！
还有更好的算法吗？思考ing···