题解 | 质数因子

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]))

全部评论

相关推荐

06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务