求质数的算法教程
求质数的算法 比如,求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···