< uruneaさんのAI生成コード置き場

高速素因数分解

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

NN = 2 * 10**5 + 10
spf = list(range(NN))  

for i in range(2, int(NN**0.5)+1):
    if spf[i] == i:
        for j in range(i*i, NN, i):
            if spf[j] == j:
                spf[j] = i

def fast_factorize(x):
    res = []
    while x > 1:
        res.append(spf[x])
        x //= spf[x]
    return res