高速素因数分解

ある数xが素数かどうかtrue/falseのテーブルを持つ代わりに、xを割り切る最小の素数のテーブルを作る

code:python

def precompute(AS)

maxAS = max(AS)

for p in range(2, maxAS + 1):

continue

# p is prime

x = p * p

while x <= maxAS:

x += p

return eratree

O(N log log N)

x = p * p

これより小さいものはもし合成数ならpより小さい約数を持つので。

実際に素因数分解をする時には1になるまでテーブル引きと割り算をすれば良い

これがlog Nなので高速

sqrt N以下の素数で割るのより高速、ただし前処理が必要なので、たくさん素因数分解する場合向き

code:python

for a in AS:

factors = []

while a > 1:

factors.append(d)

a //= d

...

ちなみに「xを割り切る最小の素数のテーブル」にするためにループをNまで走ってるが「最小の素数もしくは0、0の時はxが素数」とするならループはsqrt Nまでで良い

多少は速くなる

素因数分解のところで場合わけが必要になる