高速な素因数分解 - 数学/競プロメモ

問題

題材は以下の問題です。

https://codeforces.com/contest/1047/problem/C

概要

ある数 $n$ を素因数分解をするとき、通常は $\sqrt n$ までの素数で順に割ればよい。これは計算量 $\sqrt n$ で求めることができる。

今回の場合は、配列 $a_n$ に含まれる $a_i$ のすべての数について素因数分解する必要がある。通常の方法で素因数分解すると $O(n \sqrt n)$ となって 1sec の制約だと TLE してしまう。複数の数を高速に素因数分解する手段が必要である。

minFactor[i] := $i$ に含まれる最小の素因数

とすると、これは事前に [1, MAX] のそれぞれの数 $i$ について minFactor[i] を求めておくことで、数 $n$ を素因数分解する際に、minFactor[i] を用いて $n$ の素因数のみによって割っていくことができる。したがって通常の素因数分解よりも高速に素因数分解することができる。（ただしメモリの制約上 MAX の値が $10^8$ 程度までにおさまる必要がある）