黑马程序员技术交流社区

标题: 打印1000以内的所有质数,程序那里有问题 [打印本页]

作者: 探索者    时间: 2015-5-23 21:41
标题: 打印1000以内的所有质数,程序那里有问题
结果总是出不来,程序那里有问题?

  1. /*
  2. 需求:打印出1000以内的所有质数。

  3. 思路:
  4.         用第一个循环去从2开始遍历1000以内的所有数,并第二层循环去判断所遍历的数是不是质数,
  5.         要判断遍历的数是不是质数,只需整除完从2到自身的一半的数即可,如果都没有被整除,则
  6.         该数为质数,否则不为质数。
  7. */

  8. class ZhiShuDemo
  9. {
  10.         public static void main(String[] args)
  11.         {
  12.                 printZhiShu(1000);
  13.         }

  14.         public static void printZhiShu(int key)
  15.         {
  16.                 int count=0,flag=0;//定义一个计数器和标记;
  17.                 for (int x=2;x<=key ;x++ )//对2到1000的数进行遍历;
  18.                 {
  19.                         if((x/2)<2)//对于数值除以2的结果不超过的2的数,可判断为质数,计数器加1,并打印;
  20.                                 {
  21.                                         count++;
  22.                                         System.out.println(x+"--"+count+" ");
  23.                                 }
  24.                         else
  25.                         {
  26.                                 for (int y=2;y<=(x/2) ;y++ )//判断是否为质数,只需整除完2到自身的一半;
  27.                                 {
  28.                                         if ((x%y)==0)
  29.                                         {
  30.                                                 flag=1;//如果能够被整除,标志置为1;
  31.                                                 break;//跳出当前循环;
  32.                                         }
  33.                                        
  34.                                 }
  35.                                 if (flag==0)//如果标志为0,则计数器加1,并打印该质数和累加的次数;
  36.                                 {
  37.                                         count++;
  38.                                         System.out.println(x+"--"+count+" ");
  39.                                 }
  40.                         }
  41.                 }
  42.         }

  43. }
复制代码



作者: 探索者    时间: 2015-5-23 22:00
刚刚自己已经检查出来了,是标志被置为1后,跳出循环,没有进行标志重新置0导致的,刚试了1000以内的,效率还行,但是查找更大的数,比如100000到110000的所有质数,效率就太低,有没有大神有更好的思路和相应代码,使得效率更高一点?
作者: qq496099229    时间: 2015-5-23 22:44
探索者 发表于 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);
                        }
                }
        }
}
作者: 探索者    时间: 2015-5-24 10:29
本帖最后由 探索者 于 2015-5-24 10:33 编辑
qq496099229 发表于 2015-5-23 22:44
/*
* 需求:打印出1000以内的所有质数。

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


作者: qq496099229    时间: 2015-5-24 10:33
探索者 发表于 2015-5-24 10:29
思路不错:
1.递增+2;因为偶数不可能是质数:

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

恩,那两点都改善的比较好,能不能做到只整除2到sqrt()之前的所有质数,这样效率是不是会更好?
作者: 别想太多    时间: 2015-5-24 10:43
标志被置为1后,跳出循环,没有进行标志重新置0
作者: qq496099229    时间: 2015-5-24 10:47
探索者 发表于 2015-5-24 10:37
恩,那两点都改善的比较好,能不能做到只整除2到sqrt()之前的所有质数,这样效率是不是会更好? ...

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

要实现你说的整除质数,或许可以这样,,你把之前是质数的,存储在数组里面,然后i去遍历数组的数去整除。
作者: 南朝小和尚    时间: 2015-5-24 10:54
/*
思路:将1-1000存入array[1001]的数组,然后从中踢出1,2,3,4····的倍数
*/
作者: 探索者    时间: 2015-5-24 10:59
别想太多 发表于 2015-5-24 10:43
标志被置为1后,跳出循环,没有进行标志重新置0

恩,已经发现了
作者: 探索者    时间: 2015-5-24 11:01
qq496099229 发表于 2015-5-24 10:47
把2单独拿出来除,然后再整除3到sqrt()的奇数或许可以

要是只整除3到sqrt()的所有质数呢?有没有更好的方法
作者: 探索者    时间: 2015-5-24 11:04
qq496099229 发表于 2015-5-24 10:51
要实现你说的整除质数,或许可以这样,,你把之前是质数的,存储在数组里面,然后i去遍历数组的数去整除 ...

用数组去存储遍历到的质数,然后再整除数组的所有质数,其实这个方法我也有想过,只是觉得要是数比较大的话,数组就得非常大 ,有局限性
作者: 探索者    时间: 2015-5-24 11:09
南朝小和尚 发表于 2015-5-24 10:54
/*
思路:将1-1000存入array[1001]的数组,然后从中踢出1,2,3,4····的倍数
*/

用数组去存储确实可以,只是对于比较大的数,数组就得非常大
作者: qq496099229    时间: 2015-5-24 11:24
探索者 发表于 2015-5-24 11:04
用数组去存储遍历到的质数,然后再整除数组的所有质数,其实这个方法我也有想过,只是觉得要是数比较大的 ...

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

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

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

而不是像你这样给一个算法弄一个很大数,去和一个很小的数比较。。。。
作者: 探索者    时间: 2015-5-24 11:54
qq496099229 发表于 2015-5-24 11:24
你要用到之前的质数,那肯定要存储的,算法极大的减少了时间复杂度,但是内存会增加。当然还可以用集合存 ...

恩,刚才又思考了一下,在你优化的那两点的基础上,又优化了第三点:
  3.在遍历2到sqrt()的所有数的时候,可以把增量增加为2,即从3开始遍历,每次增加2,直到sqrt()即可,
    因为质数本身是奇数,一定不能整除偶数,所以只要判断是否能整除所有的奇数就可以了。
作者: 南朝小和尚    时间: 2015-5-24 17:21
探索者 发表于 2015-5-24 11:09
用数组去存储确实可以,只是对于比较大的数,数组就得非常大

大数不就是用数组存储么,比如高精度的算术都是利用数组来完成
作者: 柒仴、看雲佉    时间: 2015-5-24 20:56
虽然看不懂但是感觉好厉害的样子




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2