高速素因数分解

num = 10 ** 6 #素因数分解したい最大の数
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
P = primes(num)

yaku = [1 for _ in range(num+1)]
for i in P:
    k = int(10**6 / i)
    for j in range(1,k+1):
        if i > 1 and yaku[i*j] == 1:
            yaku[i*j] = i

def prime(a):
    ans = set()
    while yaku[a] != 1:
        ans.add(yaku[a])
        a = int(a/yaku[a])
    return ans
print(prime(24))->{2,3}