今天有人给出了一道分解质因数的题目:从键盘输入一个正整数,对其进行因数分解,例如10=2*5,60=2*2*3*5。
给出一段简明易懂的代码(此处稍作简化处理):
#算法1:一重循环,简单直接
num = int(input("请输入要分解的正整数:"))
result = []
x = num
i = 2
while True:
if x == 1:
break
if x % i == 0:
result.append(i)
x /= i
else:
i += 1
print(num, '=', '*'.join(map(str, result)))
该算法的主要思想是设置一个死循环,不断分解质因数i,并把整除的商作为新的被除数x,直到被除数x的值变成1为止,此时分解结束,跳出循环。
算法1简单明了,但是循环体内的if条件判断和while循环条件判断有些重复,可以把修改循环条件,并把循环体内的条件语句改成while循环语句,使用一个二重循环,可以减少条件判断,并使代码更简洁。改进后代码如下:
#算法2:二重循环,可以减少条件判断,并使代码更简洁
num = int(input("请输入要分解的正整数:"))
result = []
x = num
i = 2
while x >= i:
while x % i == 0:
result.append(str(i))
x //= i
i+= 1
print(f'{num} ={"*".join(result)}')
当输入num = 999999999999999时,算法1耗时0.671秒,而算法2耗时0.641秒,有了微弱的进步。
能不能进一步改进呢?
回想起在判断某个整数是否为质数时,我们曾经采用过缩小因数i的枚举范围的方法。在算法1和算法2中,因数i的枚举范围均为[2, x],当x是大质数时,效率很低。我们可以缩小因数i的枚举范围为[2, int(x**0.5)],以便提高算法效率。此外,为了使代码更简洁,我把外层循环写成了for循环的形式。改进后代码如下:
#算法3:二重循环,外层for循环缩小了因数i的枚举范围
num = int(input("请输入要分解的正整数:"))
result = []
x = num
for i in range(2, int(x**0.5)+1):
while x % i == 0:
result.append(str(i))
x //= i
if x > 1:#x本身就是质数
result.append(str(x))
print(f'{num} ={"*".join(result)}')
看上去代码很简洁,逻辑也很清晰,但运行结果却让我大跌眼镜!
当输入num = 999999999999999时,算法3竟然耗时3.750秒。
这究竟是怎么回事呢?
#算法4:使用递归算法,简洁高效
def fenjie(num):
x= num
i= 2
text = ""
while i < int(num ** 0.5) + 1:
if num % i == 0:
num //= i
text += f'{i}*'
return text + fenjie(num)
else:
i += 1
text += str(num)
return text
num = int(input("请输入要分解的正整数:"))
result = str(num) +" = "+fenjie(num)
print(result)
使用了递归算法,效率高的惊人,当输入num = 999999999999999时,耗时几乎为0.0秒。照理说,递归算法的效率是不如循环迭代算法的,那问题究竟出在哪里呢?
仔细观察,原来问题出在算法3的外层for循环上面,Python中for循环可以用来遍历range()函数生成的可迭代序列,该序列的值一开始就确定了,不受循环体内语句的影响,也可以简单地理解成循环的次数一开始就确定了。在本例中,算法3中可迭代序列为range(2, int(x**0.5)+1),虽然后来在循环体内修改了x的值,但不影响循环的次数。
而算法4采用了递归的方法,其参数num不断变小,则对应的因数i的上限也不断变小,从而大大提高了效率。
搞清楚原因就好办了,我们只需把算法3的外层for循环改成while循环即可,代码如下:
#算法5:把算法3的外层for循环改成while循环
num = int(input("请输入要分解的正整数:"))
result = []
x = num
i = 2
while i <= int(x**0.5):
while x % i == 0:
result.append(str(i))
x //= i
i+= 1
if x > 1:#x本身就是质数
result.append(str(x))
print(f'{num} = {"*".join(result)}')
修改了外层循环的写法以后,算法5效率大大提升,在时间上能与算法4持平,空间复杂度则更低。当输入num = 99999999999999999999999999999999时,算法4和算法5耗时均为0.046875秒,表现出相当高的效率。
至此,我们分析了分解质因数算法的优化过程,指出了提高枚举算法效率的一个重要方法就是减少枚举范围,同时还发现了Python语言中for循环结构的一个特性,希望大家在遇到此类问题时能提高警惕,避免出错。
此外,分解质因数算法在某些特定情况下还可以进一步优化,例如要分解多个整数,或被分解的整数非常大时,我们可以先制作一个质数表,然后只在质数表中枚举质因数,这样可以大大提高效率。当然,制作质数表本身也是需要时间的,我们需要根据问题的规模,选择适合的算法来处理。
-------------------------------------------------
相关文章
原创互联网未来世界企业政府通讯APP办公节约成本类似马云思维-哇谷IM
公有云和私有云之间有什么区别?类似融云、环信云、网易云、哇谷云?
IM云系统即时通讯公有云、私有云、企业云、海外云-哇谷IM团队
im即时通讯社交软件APP红包技术分析(五):微信红包、聊呗红包、诚信红包、高并发技术
im即时通讯-微信红包、支付宝红包、聊呗红包、诚信红包、谈功能逻辑、容灾、运维、架构等。Q红包
更多文章
.
企业即时通讯服务 | 商用红包功能构架 | 哇谷IM首页 | JM沟通IM下载 | IM功能与价格 | 即时通讯动态 | 热门动态 | 关于哇谷 |联系我们