结果总是出不来，程序那里有问题？

1. /*
   
2. 需求：打印出1000以内的所有质数。
   
3. 
   
4. 思路：
   
5.         用第一个循环去从2开始遍历1000以内的所有数，并第二层循环去判断所遍历的数是不是质数，
   
6.         要判断遍历的数是不是质数，只需整除完从2到自身的一半的数即可，如果都没有被整除，则
   
7.         该数为质数，否则不为质数。
   
8. */
   
9. 
   
10. class ZhiShuDemo
    
11. {
    
12.         public static void main(String[] args)
    
13.         {
    
14.                 printZhiShu(1000);
    
15.         }
    
16. 
    
17.         public static void printZhiShu(int key)
    
18.         {
    
19.                 int count=0,flag=0;//定义一个计数器和标记；
    
20.                 for (int x=2;x<=key ;x++ )//对2到1000的数进行遍历；
    
21.                 {
    
22.                         if((x/2)<2)//对于数值除以2的结果不超过的2的数，可判断为质数，计数器加1，并打印；
    
23.                                 {
    
24.                                         count++;
    
25.                                         System.out.println(x+"--"+count+" ");
    
26.                                 }
    
27.                         else
    
28.                         {
    
29.                                 for (int y=2;y<=(x/2) ;y++ )//判断是否为质数，只需整除完2到自身的一半；
    
30.                                 {
    
31.                                         if ((x%y)==0)
    
32.                                         {
    
33.                                                 flag=1;//如果能够被整除，标志置为1；
    
34.                                                 break;//跳出当前循环；
    
35.                                         }
    
36.                                        
    
37.                                 }
    
38.                                 if (flag==0)//如果标志为0，则计数器加1，并打印该质数和累加的次数；
    
39.                                 {
    
40.                                         count++;
    
41.                                         System.out.println(x+"--"+count+" ");
    
42.                                 }
    
43.                         }
    
44.                 }
    
45.         }
    
46. 
    
47. }
    

复制代码

刚刚自己已经检查出来了，是标志被置为1后，跳出循环，没有进行标志重新置0导致的，刚试了1000以内的，效率还行，但是查找更大的数，比如100000到110000的所有质数，效率就太低，有没有大神有更好的思路和相应代码，使得效率更高一点？

探索者 发表于 2015-5-23 22:00
刚刚自己已经检查出来了，是标志被置为1后，跳出循环，没有进行标志重新置0导致的，刚试了1000以内的，效率 ...

/*
* 需求：打印出1000以内的所有质数。

思路：
    2单独拿出来，不用每次都判断；   
        用第一个循环去从3开始遍历1000以内的所有数，递增+2；因为偶数不可能是质数
        并第二层循环去判断所遍历的数是不是质数，
        要判断遍历的数是不是质数，只需整除完从2到sqrt()的数即可，如果都没有被整除，则
        该数为质数，否则不为质数。
         */
public class ZhiShuDemo {
        public static void main(String args []){
                System.out.println("2");
                ss(1000);
        }
        static void ss(int aa){
                int flag=1;
                for(int i=3;i<=aa;i+=2)
                {
                        int j=2;
                        while(j<=(int)Math.sqrt(i))
                        {
                                if((i%j)==0)
                                {
                                        flag=0;
                                        break;
                                }
                                j++;
                                flag=1;
                        }
                        if(flag==1){
                                System.out.println(i);
                        }
                }
        }
}

qq496099229 发表于 2015-5-23 22:44
/*
* 需求：打印出1000以内的所有质数。

这两点思路很不错，改善的很好：
1.递增+2；因为偶数不可能是质数：2.[size=14.1666660308838px]只需整除完从2到sqrt()的数即可。
[size=14.1666660308838px]

探索者 发表于 2015-5-24 10:29
思路不错：
1.递增+2；因为偶数不可能是质数：

其实开根号那个也是减少第二个循环次数的主要

qq496099229 发表于 2015-5-24 10:33
其实开根号那个也是减少第二个循环次数的主要

恩，那两点都改善的比较好，能不能做到只整除2到sqrt()之前的所有质数,这样效率是不是会更好？

标志被置为1后，跳出循环，没有进行标志重新置0

探索者 发表于 2015-5-24 10:37
恩，那两点都改善的比较好，能不能做到只整除2到sqrt()之前的所有质数,这样效率是不是会更好？ ...

把2单独拿出来除，然后再整除3到sqrt()的奇数或许可以

qq496099229 发表于 2015-5-24 10:47
把2单独拿出来除，然后再整除3到sqrt()的奇数或许可以

要实现你说的整除质数，或许可以这样，，你把之前是质数的，存储在数组里面，然后i去遍历数组的数去整除。

/*
思路：将1-1000存入array[1001]的数组，然后从中踢出1,2,3,4····的倍数
*/

别想太多 发表于 2015-5-24 10:43
标志被置为1后，跳出循环，没有进行标志重新置0

恩，已经发现了

qq496099229 发表于 2015-5-24 10:47
把2单独拿出来除，然后再整除3到sqrt()的奇数或许可以

要是只整除3到sqrt()的所有质数呢？有没有更好的方法

qq496099229 发表于 2015-5-24 10:51
要实现你说的整除质数，或许可以这样，，你把之前是质数的，存储在数组里面，然后i去遍历数组的数去整除 ...

用数组去存储遍历到的质数，然后再整除数组的所有质数，其实这个方法我也有想过，只是觉得要是数比较大的话，数组就得非常大 ，有局限性

南朝小和尚 发表于 2015-5-24 10:54
/*
思路：将1-1000存入array[1001]的数组，然后从中踢出1,2,3,4····的倍数
*/

用数组去存储确实可以，只是对于比较大的数，数组就得非常大

探索者 发表于 2015-5-24 11:04
用数组去存储遍历到的质数，然后再整除数组的所有质数，其实这个方法我也有想过，只是觉得要是数比较大的 ...

你要用到之前的质数，那肯定要存储的，算法极大的减少了时间复杂度，但是内存会增加。当然还可以用集合存储

没有公式能直接判断一个数是不是质数。都是要遍历的

比较是相对的，同样大的数，哪个算法执行效率最优。。。这样比较才有意义

而不是像你这样给一个算法弄一个很大数，去和一个很小的数比较。。。。

qq496099229 发表于 2015-5-24 11:24
你要用到之前的质数，那肯定要存储的，算法极大的减少了时间复杂度，但是内存会增加。当然还可以用集合存 ...

恩，刚才又思考了一下，在你优化的那两点的基础上，又优化了第三点：
  3.在遍历2到sqrt()的所有数的时候，可以把增量增加为2，即从3开始遍历，每次增加2，直到sqrt()即可，
    因为质数本身是奇数，一定不能整除偶数，所以只要判断是否能整除所有的奇数就可以了。

探索者 发表于 2015-5-24 11:09
用数组去存储确实可以，只是对于比较大的数，数组就得非常大

大数不就是用数组存储么，比如高精度的算术都是利用数组来完成

虽然看不懂但是感觉好厉害的样子