A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

关于判断什么是素数的这个事儿
《前言》
        今天有同学向我询问:判断素数的那个题目,为什么要除以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

好了,和大家分享到这里,谢谢!

20 个回复

倒序浏览
杜大神,厉害啊!!!!
回复 使用道具 举报
黑马-幻灭 发表于 2015-1-8 22:49
杜大神,厉害啊!!!!

好好学习,天天向上:lol
回复 使用道具 举报
高手,厉害啊!
回复 使用道具 举报
高手,厉害啊!
回复 使用道具 举报
把我看懵了:dizzy:
回复 使用道具 举报
理解下   还是理解不透
回复 使用道具 举报

看来我表述的还是不够简练。谢谢
回复 使用道具 举报
446111220 发表于 2015-1-9 09:27
理解下   还是理解不透

哪里不理解?很简单的道理嘛,如果两个数相加等于x,那么这两个数越靠近,越接近x/2。如果是两个数相乘等于x,那么这两个数越靠近,越接近x的正平方根。
回复 使用道具 举报
对于一个大于1正数x,数学运算上必然有2*x/2=x,恒成立。
那么如果两个a,b数都大于x/2,则必然a*b>x,所以在循环到额时候用x/2判断,减少循环次数,
简单的数学上对程序优化
回复 使用道具 举报
邓士林 发表于 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:35
您确定是x/2吗?不是x的平方根吗?

x/2的是可以的,x的平方根也是可以的。
在0<x<4之间的时候x/2小于x的平方根
x>4的时候,x/2是大于x的平方根,是可以进行判断的,如果数据比较大,判断次数没有平方根筛选的快。
回复 使用道具 举报
没理解明白
回复 使用道具 举报
好像很吊的样子
回复 使用道具 举报
没怎么看直接上判断素数的代码:
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 21:56
x/2的是可以的,x的平方根也是可以的。
在0

好吧,学习了。确实可以,那样说的话,除以1-x之间的每一个数都可以喽。(貌似确实可以),就是速度慢点。
回复 使用道具 举报

慢慢理解,不急,这个不重要,作为了解。
回复 使用道具 举报

菜鸟一只。呵呵,请多指教!
回复 使用道具 举报
探寻者 发表于 2015-1-9 22:49
没怎么看直接上判断素数的代码:
public static boolean prime(int n)
        {

一种需求可以写成,很多种。
回复 使用道具 举报
顶一个  来过!!!
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马