题解 | #质数因子#

大多数同学只关注到了一开始的时候使用平方根降低复杂度，然而忽略了后续进一步的优化，假如测试用例加上2的1000次方会如何？
使用while循环会比使用for循环时间复杂度要低，for循环的条件在循环中是不可变化的，而while循环每一次都可以重新调整条件缩小范围（如果条件有变化），从而这个时间复杂度差不多是$\frac{1}{2}\log n\backslash frac\{\; 1\; \}\{\; 2\; \}\backslash log\{n\}$，而高赞题解所使用的for循环时间复杂度是$\sqrt{n}\backslash sqrt\{\; n\; \}$。
本地测试中，测试数字为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)