黑马程序员技术交流社区

标题: 寻找素数的疑问？？ [打印本页]

---

作者: 陈从宾    时间: 2012-3-21 18:48
标题: 寻找素数的疑问？？
题目：判断101-200之间有多少个素数，并输出所有素数。
1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，
则表明此数不是素数，反之是素数。

public class Test_2 {
    public static void main(String[] args) {

        // TODO 自动生成方法存根

        for(int i=101;i<=200;i++){

            for(int j=2;j<=Math.sqrt(i);j++){

                if(i%j==0)break;

                if(j>=Math.sqrt(i)-1)

                    System.out.println(i);

            }

        }

    }

}
哪位给解释一下为什么是“用一个数分别去除2到sqrt(这个数)”而不是“用一个数分别去除2到200”？

---

作者: 刘元明    时间: 2012-3-21 19:07
因为一个数分解为两个数相乘，这两个数中必然有一个数<=sqrt(这个数)，所以如果这个数有大于sqrt(这个数)的因数，那它就必然对应有个小于sqrt(这个数)的因数
选择在2到sqrt（这个数），可以减少循环次数

---

作者: 刘元明    时间: 2012-3-21 19:16

刘元明 发表于 2012-3-21 19:07
因为一个数分解为两个数相乘，这两个数中必然有一个数

呵呵，对于技术分它应该是学习的附属品，只要能够相互学习，相互交流，相信我们都能很快进黑马的，加油！

---

作者: 陈从宾    时间: 2012-3-21 19:20

刘元明 发表于 2012-3-21 19:16
呵呵，对于技术分它应该是学习的附属品，只要能够相互学习，相互交流，相信我们都能很快进黑马的，加油！ ...

对啊对啊····不要把手段当成自己的目标，学习才是我们的目标，一起加油·！！

---

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

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