前面讲了一道素数判断的题
一知半解讲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这样的例子去式。试试证明,数学不好,学编程好痛苦的!
好了,我这个问题我囫囵半片的讲完了,不知道你是不是看得云山雾罩稀里糊涂的。
一知半解讲真的就是一知半解,更多的是一种讨论和交流,和大家共同学习共同进步吧!
领取专属 10元无门槛券
私享最新 技术干货