一知半解讲python第二季：4.素数判断中的效率问题

前面讲了一道素数判断的题

一知半解讲python第二季：2.素数判断

，重点放在了flag标记变量上，并且留了一个思考：循环终止值可不可以再小一些。

先回看一下源代码吧

#coding:cp936

flag=0

n=eval(input("请输入待判断的整数："))

for i in range(2,n):#从2开始到n-1结束, 每次+1

if(n%i==0):

flag=1

break #或者i=n

if(flag==0):

print("yes")

else:

print("no")

对于这个问题我原本也是没有认识的，因为一知半解嘛！后来在某网站做题提交测试时居然没通过。提示是超时！！！一下就蒙圈了，怎么会超时呢？我的思路没错啊。冥思苦想之后，求助了一下大神。大神一点拨，我把n改为了n/2。结果这道题过了，但后来又做了一道相似的题，居然又是超时。无奈，再次请教大神。这次和大神探讨了很久，天资聪（愚）慧（钝）的我，居然费了很大劲才理（懵）解（圈），改为i*i

#coding:cp936

flag=0

n=eval(input("请输入待判断的整数："))

i=2

while(i*i

if(n%i==0):

flag=1

break

i=i+1

if(flag==0):

print("yes")

else:

print("no")

比较一下c++，感觉c++的for语句在这方面还是比python灵活的，而且还可以基本取代while：

#include

using namespace std;

int main()

{

int i,n,flag=0;

for(i=2;i*i

if(n%i==0){

flag=1;

break;

}

}

if(flag==0) cout

else cout

return 0;

}

好了，代码先说到这，接下用我一知半解的认识，说说为什么i的终止值由n到n/2再到i*i

寻找11的因数，如果按照从2到n-1的方式来解决，需要尝试9次；n/2需要尝试5次；i*i

以寻找12的因子为例，按枚举的方法，我们可以得到下表：

由因数的定义可知，一个数的因数总数成对出现的，在因数是整数的情况下，出了1和自身外，它的最小因数是2，最大因数就是2的对应因数因就是它的1/2（如果能被2整除的话）。所以第一次我的认识到此为止，觉得n/2就好了，能够缩小一般的枚举次数呢，多厉害啊！

这时候浅尝辄止的秉性发作了，所以继续犯错。其实顺着这个思路我们可以继续去考虑是否还可以缩减，观察上表我们可以发现从4开始后面的因数其实在前面已经出现过了，只不过是相反的数对而已，对这样的因数我们是不用再次判断的。而这个分界数就是sqrt（n）（即平方根），想不明白使劲想啊。我是使了很大劲也想不明白的，只好举9、16这样的例子去式。试试证明，数学不好，学编程好痛苦的！

好了，我这个问题我囫囵半片的讲完了，不知道你是不是看得云山雾罩稀里糊涂的。

一知半解讲真的就是一知半解，更多的是一种讨论和交流，和大家共同学习共同进步吧！