题解 | #质数因子#
质数因子
http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
大多数同学只关注到了一开始的时候使用平方根降低复杂度，然而忽略了后续进一步的优化，假如测试用例加上2的1000次方会如何？
使用while循环会比使用for循环时间复杂度要低，for循环的条件在循环中是不可变化的，而while循环每一次都可以重新调整条件缩小范围（如果条件有变化），从而这个时间复杂度差不多是，而高赞题解所使用的for循环时间复杂度是。
本地测试中，测试数字为2的60次方时，while循环用时0秒，高赞for循环用时107.0277秒。狗头保命
import math
num = int(input())
s = ''
prime = 2
while prime < math.sqrt(num)+1:
if num%prime != 0:
prime += 1
else:
num = num //prime
s += str(prime)+' '
prime = 2
if num>=2:
s += str(num)+' '
print(s)
查看13道真题和解析