Java打印出质数的个数以及代码优化

Java打印出质数的个数以及代码优化 质数的定义

质数又称素数，定义为一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数。

初始方式：

public class PrimeNumber {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis(); //获取开始时间
        int count = 0;
        for (int i = 2; i <= 50000; i++) {//遍历50000以内的数
            boolean isFlag = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;        //标识i是否被除尽,一旦除尽,修改值
                }
            }
            if (isFlag == true) {
                count++;
            }
        }
        System.out.println("质数个数为:" + count);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms"); //输出程序运行时间
    }
}

运行结果:
质数个数为:5133
程序运行时间：3987ms

优化一：

 for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;
                    break;//已经除尽后直接结束本次循环,不再运算后续的数
                }
            }

运行结果:
质数个数为:5133
程序运行时间：455ms

优化二：

  for (int j = 2; j < Math.sqrt(i); j++) {//Math.sqrt(i)表示i的算术平方根
                if (i % j == 0) {
                    isFlag = false;
                    break;//已经除尽后直接结束本次循环,不再运算后续的数
                }
            }

质数个数为:5181
程序运行时间：9ms
只算到算术平方根的原因: 假如一个数N是合数，它有一个约数a, a×b=N
则a、b两个数中必有一个大于或等于根号N，一个小于或等于根号N。
因此，只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数。