黑马程序员技术交流社区

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

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

/*
需求：打印出1000以内的所有质数。
思路：
用第一个循环去从2开始遍历1000以内的所有数，并第二层循环去判断所遍历的数是不是质数，
要判断遍历的数是不是质数，只需整除完从2到自身的一半的数即可，如果都没有被整除，则
该数为质数，否则不为质数。
*/
class ZhiShuDemo
{
public static void main(String[] args)
{
printZhiShu(1000);
}
public static void printZhiShu(int key)
{
int count=0,flag=0;//定义一个计数器和标记；
for (int x=2;x<=key ;x++ )//对2到1000的数进行遍历；
{
if((x/2)<2)//对于数值除以2的结果不超过的2的数，可判断为质数，计数器加1，并打印；
{
count++;
System.out.println(x+"--"+count+" ");
}
else
{
for (int y=2;y<=(x/2) ;y++ )//判断是否为质数，只需整除完2到自身的一半；
{
if ((x%y)==0)
{
flag=1;//如果能够被整除，标志置为1；
break;//跳出当前循环；
}
}
if (flag==0)//如果标志为0，则计数器加1，并打印该质数和累加的次数；
{
count++;
System.out.println(x+"--"+count+" ");
}
}
}
}
}

复制代码

作者: 探索者 时间: 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