题解 | 质数因子

import sys
from functools import lru_cache
from math import sqrt

@lru_cache(maxsize=None)
def isPrime(x:int) -> bool:
    if x < 2:
        return False
    if x == 2 or x == 3:
        return True
    for i in range(2, int(sqrt(x)) + 1):
        if isPrime(i):
            if x % i == 0:
                return False
    return True
   
raw_input = []
for i,line in enumerate(sys.stdin):
    raw_input.append(line.strip())
    if i == 1:
        break

num = int(raw_input[0])
res_lst = []
for i in range(2, int(sqrt(num)) + 1):
    if isPrime(num) or num == 1:
        if num != 1:
            res_lst.append(num)
        break
    if isPrime(i):
        while num % i == 0:
            res_lst.append(i)
            num = num // i
    else:
        continue

print(' '.join([str(i) for i in res_lst]))