求100以内的质数

说明

第一次写****博客，一方面是记录自己学习复习，另一方面是向各位大牛学习，如有更优的算法，还望不吝赐教。
这是一个入门级的编程问题，常见的是求100以内的质数，这里为了能更好的体现算法的重要性，选择使用100000以内的质数

定义法

public class PrimeNumber {
    public static void main(String[] args) {
        boolean isFlag=true;                            //标识i是否被j除尽，一旦除尽，修改其值
        long start=System.currentTimeMillis();          //获得当前时间距离1970-01-01 00：00:00的毫秒时间
        System.out.print("100000以内的质数有：");
        for(int i=2;i<=100000;i++){                     //检验100000以内的质数，最小质数为2
            for(int j=2;j<i;j++){                       //根据质数的定义，检验是否只能被1和本省整除
                if (i%j==0){                            //出现非本数整除，则不是质数
                    isFlag=false;
                }
            }
            if (isFlag==true){
                System.out.print(i+" ");                 //输出质数
            }
            isFlag=true;                                 //重装isFlag的值为true，是的能够检验质数
        }
        long end=System.currentTimeMillis();
        System.out.println();                            //换行
        System.out.println("花费的时间为："+(end-start));   
    }
}

运行时间（毫秒）：

优化一：break

public class PrimeNumber {
    public static void main(String[] args) {
        boolean isFlag=true;                            //标识i是否被j除尽，一旦除尽，修改其值
        long start=System.currentTimeMillis();          //获得当前时间距离1970-01-01 00：00:00的毫秒时间
        System.out.print("100000以内的质数有：");
        for(int i=2;i<=100000;i++){                     //检验100000以内的质数，最小质数为2
            for(int j=2;j<i;j++){                       //根据质数的定义，检验是否只能被1和本省整除
                if (i%j==0){                            //出现非本数整除，则不是质数
                    isFlag=false;
                    break;                              //优化一：当出现整除数时停止循环
                }
            }
            if (isFlag==true){
                System.out.print(i+" ");                 //输出质数
            }
            isFlag=true;                                 //重装isFlag的值为true，是的能够检验质数
        }
        long end=System.currentTimeMillis();
        System.out.println();                            //换行
        System.out.println("花费的时间为："+(end-start));
    }
}

优化一运行时间（毫秒）：

优化二：Math.sqrt（）

public class PrimeNumber {
    public static void main(String[] args) {
        boolean isFlag=true;                            //标识i是否被j除尽，一旦除尽，修改其值
        long start=System.currentTimeMillis();          //获得当前时间距离1970-01-01 00：00:00的毫秒时间
        System.out.print("100000以内的质数有：");
        for(int i=2;i<=100000;i++){                     //检验100000以内的质数，最小质数为2
            for(int j=2;j<Math.sqrt(i);j++){            //优化二，使用Math.sqrt()再次减少检测的范围。math.sqrt()返回正确舍入的 double 值的正平方根。
                if (i%j==0){                            //出现非本数整除，则不是质数
                    isFlag=false;
                    break;                              //优化一：当出现整除数时停止循环
                }
            }
            if (isFlag==true){
                System.out.print(i+" ");                 //输出质数
            }
            isFlag=true;                                 //重装isFlag的值为true，是的能够检验质数
        }
        long end=System.currentTimeMillis();
        System.out.println();                            //换行
        System.out.println("花费的时间为："+(end-start));
    }
}

优化二运行时间（毫秒）：

仅输出个数版本：减少输出所花耗的时间，仅输出个数

public class PrimeNumber {
    public static void main(String[] args) {
        boolean isFlag=true;                            //标识i是否被j除尽，一旦除尽，修改其值
        int count=0;                                    //记录质数的个数
        long start=System.currentTimeMillis();          //获得当前时间距离1970-01-01 00：00:00的毫秒时间
        System.out.print("10000以内的质数有：");
        for(int i=2;i<=10000;i++){
            for(int j=2;j<Math.sqrt(i);j++){            //优化二，使用Math.sqrt()再次减少检测的范围，math.sqrt()返回正确舍入的 double 值的正平方根。
                if (i%j==0){
                    isFlag=false;
                    break;                             //优化一，当发现非质数时，及时停止测试
                }
            }
            if (isFlag==true){
                count++;
            }
            isFlag=true;
        }
        long end=System.currentTimeMillis();
        System.out.println(count+"个");                 //优化三，依次输出每个质数，画好时间
        System.out.println();
        System.out.println("花费的时间为："+(end-start));
    }
}

运行时间（毫秒）：

本文地址：https://blog.****.net/Herpetologist/article/details/109999659