费马大定理的Python简单验证
2021-08-06王德贵刘洋
电脑报 2021年29期
王德贵 刘洋
在Python的学习过程中,通过编写程序来解决一些实际问题,也是一种乐趣。在数学史上,关于数论的著名世界难题很多,了解数学家们如何破解这些难题让人深受启发和鼓舞。今天我们就用Python来简单地验证费马大定理。
一、费马大定理简介
费马大定理,又称费马问题,是数论中最著名的世界难题之一。
概括来说就是当整数n>2时,关于x,y,z的方程xn+yn=zn,无正整数解。
你看这个方程是不是和求勾股数的类似,只是2次方变成了n次方,我们后面的验证,也是根据这个思路进行的。
二、创意来源
看到这个定理内容,就想到了勾股数,我们用Python编写程序,在一定取值范圍内验证费马大定理。
如果想了解更深入的知识,大家可以参考相关资料。今天我们利用Python只做简单的验证。
三、设计思路
根据《趣味数学——勾股数》一文的分析,勾股数是平方,这里就变成了大于2的正整数,程序设计不难,验证的范围越大,幂次越高,时间复杂度会几何级数增大,大家可以自行测试。
四、程序设计
1. 费马大定理:
根据勾股数的例子,我们不难写出Python程序。代码如图1。

程序中有三重for循环,外层循环,即是输入的最大范围,然后再确定指数幂,在1~n整数范围内逐个验证,如果有满足条件的x,y,标记s=1,然后输出屏幕,否则继续验证,如果s=0的值没有改变,即没找到任何满足条件的数,则输出无整数解(图2)。

2. 时间复杂度(等级考试四级内容)
在循环的开始和结束,加上计时器,测试发现,指数为3时,在100范围内耗时大约0.28秒,200范围内耗时1.94秒,500范围内耗时36.28秒。而……
登录APP查看全文
