一知半解讲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这样的例子去式。试试证明,数学不好,学编程好痛苦的!

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181105G0G3OW00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券