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

1 
2	public static void main(String[] args) {
3		int x,y;
4		int k=0;
5		for(x=2;x<=1000;x++) {  //1~1000的素数从2开始
6			boolean flag=true;
7			for(y=2;y<x;y++) {
8				if(x%y==0) {
9					flag=false;
10					break;
11				}
12			}//判断是否是素数
13			if(flag) {
14				k++;//如果是素数，k+1
15				System.out.print(y+"\t");
16				if(k%5==0) 
17					System.out.println(x);//每5个进行输出
18			}
19		}
20		}
21	}
22

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

改进后的代码：

1  public class Su2 {
2	public static void main(String[] args) {
3		int k=0;//计数
4		System.out.println("2 ");
5		for (int i = 3; i <= 1000; i=i+2) {//外层被除数 ,因为偶数不可能是素数，所以直接+2
6
7			if(isPrime(i))//在main方法中调用isPrime(int p)
8			{
9				k++;
10				System.out.print(i);
11			if(k%5==0) 
12					System.out.println("\n");//每5个进行转行
13
14			}
15			
16		}
17	}
18	public static boolean isPrime(int p){//把判断是否是素数重新写一个方法里
19		for (int j = 3; j <= Math.sqrt(p); j++) {//内层除数,利用Math.sqrt求i的平方根可以减少循环次数
20
21			if(p % j == 0)
22				return false;
23		}
24		return true;
25	}
26}