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);
        }
}

取出的那一部分被我注释了，写了那么久，让大家帮我想想办法吧。

你是想要优化求素数的代码吧？？

胡永城 发表于 2013-12-29 14:18
你是想要优化求素数的代码吧？？

嗯，之前老师讲的时候就说了一点优化，今天同学给我说素数，我才想起来素数我之前没写出来，然后今天就试试来写。然后又试试优化了。

基本上，大多数2，3，5的倍数可以直接过滤，难点在于素数积的那些合数比如判断11413 = 101 * 113
1. 偶数
2 * n: x & 1 == 0
2. 5整除 (尾数0被偶数过滤)
5 * n: x % 10 == 5
3. 3整除
3 * n: x % 3 == 0
以上没有难度容易判断，剩下就是重点部分。
单纯步长加1循环性能会随数字范围增大而严重下降，这里先提一个概念：孪生素数。可以查一下新闻，好像前段时间一个华裔数学家给出了证明：素数往往相伴而生，间隔为2，比如11-13、41-43、101-103……另外有个证明，素数之间的间隔为6，比如11-17、41-47，可以在网上搜到该论文。第三，合数如果有最大质数因子，不会大于其平方根。至此，基于现有的前提条件可以优化循环过程。


------以上资源来源与网络------

胡永城 发表于 2013-12-29 14:48
基本上，大多数2，3，5的倍数可以直接过滤，难点在于素数积的那些合数比如判断11413 = 101 * 113
1. 偶数
2 ...

                谢谢了

不知道这个有没有用
/*
        打印 1-100 之间的所有素数
        素数: 有且仅有两个正约数的整数. 即 2 ~ i-1 之间没有一个是其约数.
*/
public class Prime02{
        public static void main(String[] args){
                //标记一个整数是素数. true 表示是一个素数, false 表示不是素数.
                boolean flag = true;
                for(int i = 2; i <= 100; i++){
                        flag = true;
                       
                        /**
                         * 16
                         *
                         * 2  8
                         * 3
                         * 4  4
                         * 5
                         * 7
                         * 8  2
                         *
                         *
                         */
                       
                        //从 2 循环到 i-1, 检验每一个数是否为 i 的约数.  
                        for(int j = 2; j <= Math.sqrt(i); j++){
                                if(i % j == 0){
                                        flag = false;
                                        //结束这次循环.
                                        break;
                                }
                        }
                        if(flag){
                                System.out.println(i);
                        }
                }
        }
}