输出100000以内的所有质数

质数：也叫素数，只能被1和他本身整除的自然数

最小的质数：2

方法一：效率很低

public class PrimeNumber { public static void main(String[] args) { boolean b = true; //遍历100以内的自然数 for (int i = 2; i <= 100; i++) { //j：被i除 for (int j = 2; j < i; j++) { if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b) { System.out.print(i + " "); } b = true; } } }

输出结果：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

实际上，上面的这种方法基本上是效率最低的。但因为100实在是太小了，计算机的运算速度很快就能计算出100以内的质数，所以现在我们不改变算法的结构，把100换成10万试试。

继续方法一：

public class PrimeNumber { public static void main(String[] args) { //获取当前时间距离1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); boolean b = true; //遍历100以内的自然数 for (int i = 2; i <= 100000; i++) { //j：被i去除 for (int j = 2; j < i; j++) { if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b) { System.out.print(i + " "); } b = true; } //获取当前时间距离1970-01-01 00:00:00的毫秒数 long end = System.currentTimeMillis(); System.out.println("\n花费时间：" + (end - start)); //6243毫秒 } }

运行结果：

用以上这种方法，输出10万以内的质数居然用了6243毫秒，即6.3秒。在真实开发中。这么慢的速度是绝对不允许的。

所以接下来对这个算法进行优化

方法二：

优化一：使用break更快地跳出循环

public class PrimeNumber { public static void main(String[] args) { //获取当前时间距离1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的自然数 for (int i = 2;i<=100000;i++){ boolean b = true; for (int j=2;j<i;j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; break;//优化一：只对本身非质数的自然数是有效的 } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n花费时间："+(end-start)); //优化一后：花费时间 619ms } }

这一次，我在最内层的if语句中加入了 break;

这样做的目的是让非质数更快的跳出循环，比如for循环到了100，此时i=100，进入第二个for循环，此时j=2，100%2=0，于是马上就break出了循环

运行结果：

可以看到，优化过后的速度立马就上来了，用时615毫秒。

方法三：

既然能对非质数进行优化，那是否可以对质数进行优化呢？当然可以

优化二：对本身是质数的自然数进行优化

public class PrimeNumber { public static void main(String[] args) { //获取当前时间距离1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的自然数 for (int i = 2;i<=100000;i++){ boolean b = true; //优化二：对本身是质数的自然数是有效的 for (int j=2;j<Math.sqrt(i);j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n花费时间："+(end-start)); //优化二：122ms } }

运行结果：

可以看到，现在运行结果相比优化一又快了，用了122ms。

方法四：

最终优化：把优化一和优化二结合。

public class PrimeNumber { public static void main(String[] args) { //获取当前时间距离1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的自然数 for (int i = 2;i<=100000;i++){ boolean b = true; //优化二：对本身是质数的自然数是有效的 for (int j=2;j<Math.sqrt(i);j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; break;//优化一：只对本身非质数的自然数是有效的 } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n花费时间："+(end-start)); //优化一加优化二：33ms } }

运行结果：

两种算法优化结合在一起效果不言而喻，输出10万以内的质数仅用了33毫秒

试除法

int N = 29; //任意选择一个 N，以29为例 int flag = 1; //flag记录 N 的属性。1 代表 N 是质数， 0 则代表不是。我们先默认它是 for(int i = 2;i < N;i++){ if(N % i == 0){ //当 N 除以 i 的余数为 0，说明 N 被 i 整除，即 N 为合数 flag = 0; break; //因为 N 已经被证明是合数，不需要再继续运算了，跳出循环 } } //算法结束，最终 flag 为 1 表示质数，flag 为 0 表示合数。

int N = 29; int flag = 1; if(N % 2 == 0) flag = 0; //首先测试 N 是否是偶数 else for(int i = 3;i * i < N;i += 2){ //与刚才不同的是，我们先从 3 开始，每次增加 2，一直 //到根号下 N 为止。这样我们的测试就在奇数中展开 if(N % i == 0){ flag = 0; break; } } //算法结束，最终 flag 为 1 表示质数，flag 为 0 表示合数。