\(N!\) を素因数分解する. \(1 \dots N\) をそれぞれ素因数分解して合成すればいい.

素因数分解した結果が \(p_1^{q_1} p_2^{q_2} \cdots p_k^{q_k}\) になったとすると, 約数の個数は \((q_1+1)(q_2+1)\cdots(q_k+1)\) である.