Java：输出1~20000内的所有素数，按每行5个打印出来 3年前

copy
public static void main(String[] args) {
        int x,y;
        int k=0;
        for(x=2;x<=1000;x++) {  //1~1000的素数从2开始
            boolean flag=true;
            for(y=2;y<x;y++) {
                if(x%y==0) {
                    flag=false;
                    break;
                }
            }//判断是否是素数
            if(flag) {
                k++;//如果是素数，k+1
                System.out.print(y+"\t");
                if(k%5==0) 
                    System.out.println(x);//每5个进行输出
            }
        }
        }
    }

分析：函数中最费时的部分是对素数的判断，因为这里有嵌套的双循环，增加了算法的时间复杂度，可以从三个方面改进： 1、 对素数的判断仿佛进行改进，从判断除以本身能否除尽，改进为除以本身数字的平方 2、 减少循环次数，因为偶数不可能是素数，所以x直接+2 3、 把判断是否是素数重新写一个方法里，然后在main方法中调用

改进后的代码：

copy
public class Su2 {
    public static void main(String[] args) {
        int k=0;//计数
        System.out.println("2 ");
        for (int i = 3; i <= 1000; i=i+2) {//外层被除数 ,因为偶数不可能是素数，所以直接+2

            if(isPrime(i))//在main方法中调用isPrime(int p)
            {
                k++;
                System.out.print(i);
            if(k%5==0) 
                    System.out.println("\n");//每5个进行转行

            }

        }
    }
    public static boolean isPrime(int p){//把判断是否是素数重新写一个方法里
        for (int j = 3; j <= Math.sqrt(p); j++) {//内层除数,利用Math.sqrt求i的平方根可以减少循环次数

            if(p % j == 0)
                return false;
        }
        return true;
    }
}