黑马程序员技术交流社区

标题: 关于判断什么是素数的这个事儿~~个人总结 [打印本页]

---

作者: 羽狼之翼    时间: 2015-1-8 22:41
标题: 关于判断什么是素数的这个事儿~~个人总结
关于判断什么是素数的这个事儿
《前言》
        今天有同学向我询问：判断素数的那个题目，为什么要除以2~（这个数的平方根）（这个数后面用x代表）？
我听了以后，镇定自若的回答道：这个问题，我也不知道（哈哈，实在抱歉真的没有研究过为什么那么做...）
我说我看过那个题目，知道是用一个叫做Math.sqrt(x)的函数，该函数返回一个x的数学正平方根，但是为
什么要依次除以2~（x的平方根），进行判断呢？
        我随后就自己琢磨了琢磨，推算了下规律，还真被我破解了。（虽然不是什么很难的问题，但毕竟能找出原理，
并帮助到了同学，是件很开心的事。）下面就给大家分析下，为什么要依次除以2~（x的平方根）进行判断。


原题目：判断101-200之间有多少个素数，并输出所有素数。
1、什么叫素数：素数就是质数，该数除了1和它本身以外不再有其他的因数。
2、那么问题来了，怎么判断呢？

我把1~14的这些数字都拆了拆，发现，偶数肯定不是素数，因为它至少有4个因数：1、2、x/2、x
那么剩下的就是看奇数了。其实这里不用区分偶数和奇数，一视同仁，咱们一起分析分析：

分析：
A：明确第一点，这里要计算的是看看两个数字相乘是否等于x，而不是2个或2个以上的数相乘等于x，所以，
第一点我们知道这里共涉及2个变化的数，我们用a、b表示，即判断除了1、x外，是否还有a*b=x存在。
B：直接分析a*b不太好理解，我们换一种角度先来看看如果是要判断a+b是否等于x的情况：

辅助分析1：如果a+b=x,那么a和b势必有一个值是大的，有一个值是小的，比如3+5=8,3是小的，5是大的。
那么这里所谓的大和小，临界点（即中间值）是哪个数字呢，很明显是相对于8的一半（即数字4）来说的，而且如果a+b=8成立，
那么a和b肯定是一个在4的左边，一个在4的右边（这里a!=b），他们是互相对应的一对儿。这里明白了，下面的分析就很容易理解了。

好了，回来看我们的题目，分析：

如果a*b=8成立，那么a和b肯定也是有一个数是大的，有一个数是小的，临界点（即中间值）是哪儿呢？当然是a和b越接近，
它俩就越靠近临界点了，当a=b，且a*b=8的时候，临界点就是a（或b）喽，很明显，这个临界点就是8的正平方根。

示例：2*2=4,3*3=9，那么8的正平方根处于2~3之间，是个小数，是2点几。因为2*4=8,2和4是不是处于临界点的两边了呢？

那么如果在2~（x的正平方根）区间内，有一个值a满足了a*b=x，那么b和a就是对应的一对儿，且b处于（x的正平方根）~x之间，
这个时候，x就肯定不是素数了，因为它有了1、a、b、x至少4个因数。

嗯哼？现在是否明白了，为什么要依次除以2~（这个数的正平方根）了吗？

1：1
2：1、2
3：1、3
4：1、2、4
5：1、5
6：1、2、3、6
7：1、7
8：1、2、4、8
9：1、3、9
10:1、2、5、10
11:1、11
12:1、2、3、4、6、12
13:1、13
14:1、2、7、14

好了，和大家分享到这里，谢谢！

---

作者: 黑马-幻灭    时间: 2015-1-8 22:49
杜大神，厉害啊！！！！

---

作者: 羽狼之翼    时间: 2015-1-8 23:46

黑马-幻灭 发表于 2015-1-8 22:49
杜大神，厉害啊！！！！

好好学习，天天向上:lol

---

作者: 以利亚    时间: 2015-1-9 09:16
高手，厉害啊！

---

作者: 以利亚    时间: 2015-1-9 09:21
高手，厉害啊！

---

作者: 菜鸟一号    时间: 2015-1-9 09:22
把我看懵了:dizzy:

---

作者: 446111220    时间: 2015-1-9 09:27
理解下   还是理解不透

---

作者: 羽狼之翼    时间: 2015-1-9 21:25

菜鸟一号 发表于 2015-1-9 09:22
把我看懵了

看来我表述的还是不够简练。谢谢

---

作者: 羽狼之翼    时间: 2015-1-9 21:27

446111220 发表于 2015-1-9 09:27
理解下   还是理解不透

哪里不理解？很简单的道理嘛，如果两个数相加等于x，那么这两个数越靠近，越接近x/2。如果是两个数相乘等于x，那么这两个数越靠近，越接近x的正平方根。

---

作者: 邓士林    时间: 2015-1-9 21:33
对于一个大于1正数x，数学运算上必然有2*x/2=x，恒成立。
那么如果两个a，b数都大于x/2，则必然a*b>x，所以在循环到额时候用x/2判断，减少循环次数，
简单的数学上对程序优化

---

作者: 羽狼之翼    时间: 2015-1-9 21:35

邓士林 发表于 2015-1-9 21:33
对于一个大于1正数x，数学运算上必然有2*x/2=x，恒成立。
那么如果两个a，b数都大于x/2，则必然a*b>x，所以 ...

您确定是x/2吗？不是x的平方根吗？

---

作者: 邓士林    时间: 2015-1-9 21:56

羽狼之翼 发表于 2015-1-9 21:35
您确定是x/2吗？不是x的平方根吗？

x/2的是可以的，x的平方根也是可以的。
在0<x<4之间的时候x/2小于x的平方根
x>4的时候，x/2是大于x的平方根，是可以进行判断的，如果数据比较大，判断次数没有平方根筛选的快。

---

作者: eli0827    时间: 2015-1-9 22:33
没理解明白

---

作者: 只会金克斯    时间: 2015-1-9 22:45
好像很吊的样子

---

作者: 探寻者    时间: 2015-1-9 22:49
没怎么看直接上判断素数的代码：
public static boolean prime(int n)
        {
                boolean flag=false;
                if(n==1){
                        return false;
                }
                else
                {
                        for(int i=2;i*i<=n;i++)
                        {
                                if(n%i==0)
                                {
                                        flag=false;
                                        break;
                                }
                                else
                                {
                                        flag=true;
                                }
                        }
                }
                return flag;
        }
不知道跟你的想法是不是一样。。。。

---

作者: 羽狼之翼    时间: 2015-1-9 23:04

邓士林 发表于 2015-1-9 21:56
x/2的是可以的，x的平方根也是可以的。
在0

好吧，学习了。确实可以，那样说的话，除以1-x之间的每一个数都可以喽。（貌似确实可以），就是速度慢点。

---

作者: 羽狼之翼    时间: 2015-1-9 23:07

eli0827 发表于 2015-1-9 22:33
没理解明白

慢慢理解，不急，这个不重要，作为了解。

---

作者: 羽狼之翼    时间: 2015-1-9 23:08

只会金克斯 发表于 2015-1-9 22:45
好像很吊的样子

菜鸟一只。呵呵，请多指教！

---

作者: 羽狼之翼    时间: 2015-1-9 23:10

探寻者 发表于 2015-1-9 22:49
没怎么看直接上判断素数的代码：
public static boolean prime(int n)
        {

一种需求可以写成，很多种。

---

作者: 些许    时间: 2015-1-9 23:14
顶一个  来过！！！

---

作者: aa524500    时间: 2015-1-9 23:23
不错，感谢分享了

---

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

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