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