求质数的算法教程

求质数的算法 比如,求10 000 000中有多少个质数 质数是只能被1和自己整除的自然数(不包括1)。 笨办法就是一个个计算,用到两层嵌套的循环,数字一大算死人,代码如下: public class PrimeNumbers { public static void main(Stri.

求质数的算法

比如,求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···