[EP003] 큰 수의 소수분해

from typing import List
import math
from time import time

from tqdm import tqdm


def get_primes_under_siev(n: int) -> List[int]:

    root_n = int(math.sqrt(n))
    siev = {}

    siev[0] = siev[1] = 0
    siev[2] = 1

    for i in range(2, root_n + 1):
        # print(i)
        if siev.get(i, 1):
            for j in range(i + i, n + 1, i):
                siev[j] = 0
        # print(siev)

    primes = [n for n in range(2, n + 1) if siev.get(n, 1)]
    return primes


def factorize(n: int) -> List[int]:
    root_n = int(math.sqrt(n)) + 1

    primes = get_primes_under_siev(root_n)

    factors = []
    for p in primes:
        if n % p == 0:
            while n % p == 0:
                factors.append(p)
                n //= p
        if n == 1:
            break

    return factors


def solve_siev2():
    t0 = time()
    BIGNUM = 317584931803

    factors = factorize(BIGNUM)

    print(factors[-1])
    print(f"took {time() - t0:.3f} sec")


if __name__ == "__main__":
    solve_siev2()

 

에라토스테네스의 체 방법으로 어떤 수 이하의 모든 소수를 구한다.

큰 수를 위 방법으로 구한 소수들로 쭉 나누어 본다.