黑马程序员技术交流社区

标题: 数学好的来谈讨,求100-200之间质数.很有挑战的. [打印本页]

---

作者: 顾亦飞    时间: 2012-7-2 18:36
标题: 数学好的来谈讨,求100-200之间质数.很有挑战的.


在网上看到一个代码,说是取1-200之间的质数..

• public class Sshu {
•     public static void main(String[] args) {
•         int i, j;
•         for(i=101; i<=200; i+=2) {
•             for(j=2; j<i/2; j++) { //也可以使用j<i-1;
•                 if(i % j == 0) break;
•                 }
•                 if(i % j != 0) {
•                     System.out.println(i + "是素数");
•             }
•         }
•     }
• }
  

大家说说看.为什么用j<i/2也可以用作条件表达示呢, 它和j<i-1有什么区别.?   
      j<i/2 什么情况下不会满足.  j<i-1 则是到J大于100的时候不满足.  这两个条件会是相同吗?

---

作者: 蒋映辉    时间: 2012-7-2 18:39
楼主的代码没有发全哦
   这个i/2  应该是在判断是否能被整除的时候的吧  一个数如果不能被小于他的一半的数整除  那比它一半大的数也不能整除它的   所以用它的一半来判断就可以了 节约运行时间.....

---

作者: 何旭栋    时间: 2012-7-2 18:42
主要是减少判断次数，i/2可以用i>>1表示，计算机位运算效率比较高
还有，你代码挂了，看不到。。。

---

作者: 黑龙江—刘鹏    时间: 2012-7-2 20:18
哈哈 挂啦

---

作者: 蒋映辉    时间: 2012-7-2 21:37

蒋映辉 发表于 2012-7-2 18:39
楼主的代码没有发全哦
   这个i/2  应该是在判断是否能被整除的时候的吧  一个数如果不能被小于他的一半的 ...

• 
  
    for(j=2; j<i/2; j++) { //也可以使用j<i-1;
•                 if(i % j == 0) break;
•                 }
•                 if(i % j != 0) {
•                     System.out.println(i + "是素数");
•             }
  

意思是  如果I不能被小于j的一半的那些数整除  那么剩下那一半的数字也不能整除它。

---

作者: Forever。    时间: 2012-7-2 22:13


楼主这个问题其实可以说是一个数学上的问题了。素数就是除了1和他本身没有书可以被他整除。
就这个程序这么写来说。假如被除数不是一个质数他可以被2,3，4，5……好多数整除。但是他一定不会被比他的1/2还大的数字整除。因为那一定是一个假分数。比如5/3,9/6，
10/6……所以说在继续的除下去没有任何的意义了。

我觉得楼主这个方法写的非常好，我整理了一下代码做了一个小小的修改，其实也不是修改，这样更加有利于初学者看的懂：
public class Sshu {
    public static void main(String[] args) {
        int i, j;
        for(i=1; i<=200; i+=2) {
            for(j=2; j<i/2; j++) {第二个for循环实际上只循环了第一个if，其实第一个for循环的结果只有两个第一就是遇到一个可以被整除的数字，然后break。第二，就是循环完毕也没有找到一个可以被整除的
                    if(i % j == 0)
                    { //也可以使用j<i-1;
                            break;
                    }
            }
            if(i % j != 0) 在这个if这里就是判断到底是遇到了上面的那种情况，如果是第一种情况，那么如果是被整除了，就直接跳过不打印，反之打印。
            {
                System.out.println(i + "是素数");
            }
        }
    }
}


总之我觉得这个算法写的非常好！

---

作者: 顾亦飞    时间: 2012-7-2 23:14

蒋映辉 发表于 2012-7-2 21:37

  for(j=2; j

想了好久，是这么回事。应当I不能被小于I的一半那些数整除，那么后面的肯定不能整除。

---

作者: Forever。    时间: 2012-7-2 23:31

顾亦飞 发表于 2012-7-2 23:14
想了好久，是这么回事。应当I不能被小于I的一半那些数整除，那么后面的肯定不能整除。 ...

加入I=5， 他有必要再去除3了么……

---

作者: 顾亦飞    时间: 2012-7-2 23:47

Forever。 发表于 2012-7-2 23:31
加入I=5， 他有必要再去除3了么……

程序在判断过程中是用i/2来做为for循环的条件。之所以用它是为了提高效率。那I＝5去除3话的话，只不过是多进行了一次判断。

---

作者: Forever。    时间: 2012-7-2 23:53

顾亦飞 发表于 2012-7-2 23:47
程序在判断过程中是用i/2来做为for循环的条件。之所以用它是为了提高效率。那I＝5去除3话的话，只不过是 ...

我说得正是此意

---

作者: 黑马-李勇    时间: 2012-7-3 03:36
标题: j<i/2只是为了提效率。


j<i/2只是为了提效率。

---

作者: 李文龙    时间: 2012-7-3 08:46

蒋映辉 发表于 2012-7-2 21:37

  for(j=2; j

j<i/2确实是提升了效率，但这还不是最有效率的方式，最有效率的应该是 j<=Math.sqrt(i); 这只需要除到 i 的平方根就行了，举个例子，对于9来说，它的一半是4.5，它的平方根是3，这样一比较效率应该看出来了吧。

---

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

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