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