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方法中调用
改进后的代码:
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;
}
}