求质数的算法

比如，求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毫秒，决定每次运行程序时系统的软硬件情况，没有大的变化。