阿狗工具

输出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 表示合数。