動機 大きな数の階乗を直接計算機上で扱おうとすると、例えば32bitなら12の階乗までしか表現できないので、ちょっとした数字でいきなり多倍長演算が必要になってきます。 しかし、例えば $12!=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12$ は、素因数分解して $=2^{10}\times3^5\times5^2\times7^1\times11^1$ とも表現できます。 アルゴリズム 階乗を素因数分解したときに各素数が何個出現するかは、次のように容易に求められます。 $12!=1\times2\times3\times4\times5\times6\times7\times8\times9\times10\times11\times12$ には $2$ の倍数が $\lf