题解 | #质数因子#

#分解质因数
#输入：一个整数
#输出：将质因数存入prime_list列表，并以空格间隔形式输出
#复杂度：1/2 log n
import sys
import math
for line in sys.stdin:
    n=int(line)
    prime_list=[]
    while True: #单独处理质因数2，这样后续就只需要考虑奇数情况
        if n&1 :
            break
        else:
            prime_list.append(2)
            n>>=1

    i=3
    while i<math.sqrt(n)+1: #如果当前处理后的n，是合数，那么它在sqrt(n)以内必然有因子
        if not n%i:
            prime_list.append(i)
            n=int(n/i) #缩小问题规模-> log n
        else:
            i+=2
    if n!=1: # 如果处理后的n已经是质数或者1，那么上述处理流程必然失效
        prime_list.append(n)
    for i in prime_list:#输出
        print(i,end=" ")