prime_fact - shakayami/ACL-for-python GitHub Wiki

prime_fact

素因数分解を高速にしてくれます

ミラーラビン素数判定法とロー法を使っています

入力が素数ならTrue,素数でないならばFalseを返します。ミラーラビン素数判定法を使っているためヒューリスティックですが、10^18以下なら正しい結果が出ると思います。

ロー法を使って素因数分解をします。入力は自然数$N$であり、 $N=p_1^{r_1}\cdots p_k^{r_k}$ と素因数分解されるときに、 {p_i:r_i ,i=1,...,r} となるようなdefaultdictを返します。