Java输出素数

=====taoyyz小陶©版权所有=====
实验一 输出 1,000,000 之内的所有素数

要求：

  程序简单，程序运行速度较快，行列对齐美观。

思路：

  1. 只需判定2到根号i之间有无数可以让n被整除，能被2到sqrt(i)之间的数整除说明是合数，否则为素数
  2. 如果不注意上述这点，每次都循环2到n的话，当数字非常大的时候时间复杂度指数上升很可怕。
  3. 关于对齐：利用String类的format()方法格式化，并且每打印10个换一行

代码：

package com.experiment.exp1;

/**
 * @Author taoyyz(陶俊杰)
 * @Date 2021/3/2 23:55
 * @Version 1.0
 */

public class PrimeNum {
    public static void main(String[] args) {
        printPrimeNum(1_000_000);
    }

    public static void printPrimeNum(int range) {
        long start = System.currentTimeMillis();
        boolean isPrime = false; //是否素数标志
        int count = 0;  // 素数计数器

        for (int i = 2; i < range; i++) {
            if (2 > (int) Math.sqrt(i)) {
                System.out.print(String.format("%8d", i)); //利用String类的format()方法格式化字符串，固定宽度7，右对齐
                count++;
            }
            //处理4到i的数
            int num = (int) Math.sqrt(i);
            //查看i是否能被2到num之间的某个数整除
            for (int inside = 2; inside <= num; inside++) { //检查是否是素数
                if (i % inside == 0) {  //能被整除说明不是素数
                    isPrime = false;
                    break;
                } else {
                    isPrime = true; //不能被整除就暂且判定是素数然后inside++，看能不能被下一位整数整除
                }
            }
            //循环结束仍然是true，就打印这个素数
            if (isPrime) {
                System.out.print(String.format("%8d", i));
                if (++count % 8 == 0) {     //每8个数换一行
                    System.out.println();
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("\n素数个数：" + count + "消耗时间：" + (end - start) + "毫秒");
        //打印出素数结果  R7 4800H用时   IDEA≈600ms  cmd≈4s
        //只统计素数个数  R7 4800H用时   IDEA≈300ms  cmd≈230ms
    }
}

运行截图：

此处省略7万个素数

心得：

  可见，通过String类的format()方法进行格式化，配合每隔几个数就换行，整体排版还是比较整齐。并且由于内层只循环平方根次，所以即使是100万个数，仅耗时600ms，很🉑，所以一定要记得把O(n²)优化为O(n·logn)🍻

感谢阅读💗