- エラトステネスのふるいを少しいじって、試し割りなしでの素因数分解を可能にするアルゴリズム
- ある数xが素数かどうかtrue/falseのテーブルを持つ代わりに、xを割り切る最小の素数のテーブルを作る
python
def precompute(AS)
maxAS = max(AS)
eratree = [0] * (maxAS + 10)
for p in range(2, maxAS + 1):
if eratree[p]:
continue
# p is prime
eratree[p] = p
x = p * p
while x <= maxAS:
if not eratree[x]:
eratree[x] = p
x += p
return eratree
- O(N log log N)
x = p * p
- これより小さいものはもし合成数ならpより小さい約数を持つので。
- 実際に素因数分解をする時には1になるまでテーブル引きと割り算をすれば良い
- これがlog Nなので高速
- sqrt N以下の素数で割るのより高速、ただし前処理が必要なので、たくさん素因数分解する場合向き
python
for a in AS:
factors = []
while a > 1:
d = eratree[a]
factors.append(d)
a //= d
...
- ちなみに「xを割り切る最小の素数のテーブル」にするためにループをNまで走ってるが「最小の素数もしくは0、0の時はxが素数」とするならループはsqrt Nまでで良い
- 多少は速くなる
- 素因数分解のところで場合わけが必要になる