本帖最后由 刘旭升 于 2013-12-29 18:29 编辑
import java.util.*;
/*
* 思路：为素数判断条件是：除了1和本身之外没有其他质因数。
* 变量：给定一个范围。
* 第一个for循环是：取的范围里的每一个数 num ++，来进行判断是不是素数。
* 第二个for循环是：需要定义一个boolean变量。如果不能被2整除就定义范围：num/2。
* 范围：2---num/2
* ++当能被整出时就 变flag,并终止循环。
* 打印时要注意打印的对象：flag为真才打印。
* */
public class shusu {
public static void main(String[] args){
Scanner reader=new Scanner(System.in);
int a= reader.nextInt();
int counts=0;int n=1;
for(int i=2;i<a;i++){
//if(i==2)
// System.out.println(i+"是一个素数。");
boolean flag=true;
while(flag){
for(int j=2;j<i/2;j++,counts++)
if(i%j==0)
flag =false;
break;
}
if(flag){
System.out.print(i+" ");
n++;
}
}
System.out.println();
System.out.println("0到"+a+"之间的素数个数为："+n);
System.out.println("性能测试-执行次数："+counts); }
}
打印：
20
2是一个素数。
2 3 5 7 11 13 17 19 性能测试-执行次数：153
//很多人都知道的优化方法：
for(int j=2;j<i/2;j++)
打印：
20
2 3 4 5 7 11 13 17 19
性能测试-执行次数：56
当1000是两组分别为：497503 247506
继续优化：
可以想像那么就j<i/3;可以吗？我们可以试试：
打印：
【6
2 3 4 5
0到6之间的素数个数为：4
性能测试-执行次数：0 】
就是说里面有一个不是我门想要的数：4。那么他怎么存在的？
因为当4/3时，余数为1。由于只是多一个4，那么我们的任务就是去掉这个4。
这个方法就比较简单了：直接去掉。
while(flag){
for(int j=2;j<=i/3;j++,counts++)
if( i%j==0)
flag =false;
if(i==4)flag =false;
break;
} 当i为4时不打印。
打印：
20
2 3 5 7 11 13 17 19
0到20之间的素数个数为：8
性能测试-执行次数：40
可以发现性能提高不少。当为1000时：
性能测试-执行次数：165170
有人会继续猜想，j<i/4;...5..6..7...n.. 可以吗？
我觉得当我们需要运行很大的数时，用这个方法比较好。当然n的取值不要太大，大了就未必会提高性能。写到5估计会不错。：
while(flag){
for(int j=2;j<=i/5;j++,counts++)
if( i%j==0)
flag =false;
if(i==4||i==6||i==8||i==9) flag =false;
break;
} 20
2 3 5 7 11 13 17 19
0到20之间的素数个数为：8
性能测试-执行次数：15
为1000时：
性能测试-执行次数：98505
在这时候，我们会发现，出现的非素数为5*2之间的素数。
这就有了解决方案：
当我们取出10之间的素数时，
import java.util.*;
/*
* 思路：为素数判断条件是：除了1和本身之外没有其他质因数。
* 变量：给定一个范围。
* 第一个for循环是：取的范围里的每一个数 num ++，来进行判断是不是素数。
* 第二个for循环是：需要定义一个boolean变量。如果不能被2整除就定义范围：num/2。
* 范围：2---num/2
* ++当能被整出时就 变flag,并终止循环。
* 打印时要注意打印的对象：flag为真才打印。
* */
public class shusu {
public static void main(String[] args){
Scanner reader=new Scanner(System.in);
int a= reader.nextInt();
int counts=0;int n=0;//int ;
for(int i=2;i<a;i++){
//if(i==2)
// System.out.println(i+"是一个素数。");
boolean flag=true;boolean flag2=true;
while(flag){
for(int j=2;j<=i/5;j++,counts++)
if( i%j==0)
flag =false;
/*//完成取10之间的素数；
for(int x=1;x<5*2;x++){
while(flag){
for(int y=2;y<=x;y++,counts++)
if( x%y==0)
flag =true;
break;
}
}*/
if(i==4||i==6||i==8||i==9)
flag =false;
break;
}
if(flag){
System.out.print(i+" ");
n++;
}
}
System.out.println();
System.out.println("0到"+a+"之间的素数个数为："+n);
System.out.println("性能测试-执行次数："+counts);
}
}
| 
收藏
淘帖
踩
