黑马程序员技术交流社区

标题: 求质数代码 [打印本页]

---

作者: 郑飞    时间: 2014-10-20 14:37
标题: 求质数代码

1. <blockquote>import java.util.ArrayList;

复制代码

---

作者: atlas    时间: 2014-10-20 14:41
好。。。。。。。。。。

---

作者: mingtianrsm    时间: 2014-10-20 15:24
楼主，你的prime2里这个地方count = i%j!=0?count+1:count;错了，应该是count = i%j==0?count+1:count;

---

作者: mingtianrsm    时间: 2014-10-20 15:26
而prime1里面，第二个循环的判定可以改为j<=(i/2)；然后count值的判定为1，这样可以减少一半的运算

---

作者: 郑飞    时间: 2014-10-20 16:27

mingtianrsm 发表于 2014-10-20 15:26
而prime1里面，第二个循环的判定可以改为j

嗯prime1超过1000效率直线下降 网上好多优化的 上次看了一篇文章 面试这个题 面试官给分了 N个等级 还给出了答案 后面几种都不好理解 回头看看能找到就给摘过来

---

作者: 郑飞    时间: 2014-10-20 16:32

mingtianrsm 发表于 2014-10-20 15:24
楼主，你的prime2里这个地方count = i%j!=0?count+1:count;错了，应该是count = i%j==0?count+1:count; ...

"count = i%j!=0?count+1:count;
                        if(count==0)"

i%j!=0?count+1 : 这里i%质数集里的元素 !=0就是说不是质数然后count = count+1;

我下面是用count==0做为质数的条件 应该没错啊

---

作者: mingtianrsm    时间: 2014-10-21 14:06

郑飞 发表于 2014-10-20 16:32
"count = i%j!=0?count+1:count;
                        if(count==0)"

你对于!=0的判定估计弄错了，正是因为它们的余数不等于0，所以说明里面没有i的约数，所以应该用==0来当作不是质数的判定条件。

---

作者: 郑飞    时间: 2014-10-21 16:29

mingtianrsm 发表于 2014-10-21 14:06
你对于!=0的判定估计弄错了，正是因为它们的余数不等于0，所以说明里面没有i的约数，所以应该用==0来当作 ...

嗯是我弄错了 很奇怪我之前运行过都正常 估计测试的时候调用错了

---

作者: 郑飞    时间: 2014-10-21 17:12

mingtianrsm 发表于 2014-10-21 14:06
你对于!=0的判定估计弄错了，正是因为它们的余数不等于0，所以说明里面没有i的约数，所以应该用==0来当作 ...

还不止这个地方  看了下后面打印语句和add()这也要加{} 谢谢纠错哈

---

作者: hanxing    时间: 2014-11-7 17:50
楼主我怎么看不到代码呢?

---

作者: 姜浩    时间: 2014-11-7 17:54
不知道为什么，我只能看到一行代码。

---

作者: 九零零    时间: 2014-11-7 18:02
http://bbs.itheima.com/thread-71296-1-1.html
论坛里有这个贴子，里面总结的很详细，楼主可以看看

---

作者: 郑飞    时间: 2014-11-7 19:08

hanxing 发表于 2014-11-7 17:50
楼主我怎么看不到代码呢?

可能哪次改的时候没注意改成这样了 给你个平方根求质数的吧 简单易懂效率还凑活 楼上给的链接里有很详细的算法

1. public static void prime1(int num)       
   
2.         {               
   
3.                 boolean flag = true;
   
4.                 for(int i = 2;i<=num;i++)//从2开始判断
   
5.                 {
   
6.                         for(int j = 2;j<=Math.sqrt(i);j++)//除到i的平方根
   
7.                         {
   
8.                                 if(i%j==0)//如果除的尽
   
9.                                 {
   
10.                                         flag = false;//标记为假
    
11.                                         break;//已经确认当前i不是质数,跳出内循环;
    
12.                                 }
    
13.                         }
    
14.                         if(flag)//通过一遍循环如果标记为真说明i是质数
    
15.                                 System.out.print(i+" ");
    
16.                         else flag = true;//重置标记
    
17.                 }
    
18.         }

复制代码

---

作者: 九零零    时间: 2014-11-7 19:50

郑飞 发表于 2014-11-7 19:08
可能哪次改的时候没注意改成这样了 给你个平方根求质数的吧 简单易懂效率还凑活 楼上给的链接里有很详细 ...

楼主这个代码是不是应该在 if(i%j==0) flag = false;后面加一个break跳出当前for循环啊

---

作者: 郑飞    时间: 2014-11-7 21:44

九零零 发表于 2014-11-7 19:50
楼主这个代码是不是应该在 if(i%j==0) flag = false;后面加一个break跳出当前for循环啊 ...

嗯 确实 后面都在做无用功 谢谢纠错啊
改过来了

1. if(i%j==0)//如果除的尽
   
2.                                 {
   
3.                                         flag = false;//标记为假
   
4.                                         break;//已经确认当前i不是质数,跳出内循环;
   
5.                                 }

复制代码

---

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

黑马程序员IT技术论坛 X3.2