Python３で素因数分解する

素因数分解をライブラリで行う

from sympy.ntheory import factorint

これが正体． 詳細は，

Number Theory — SymPy 1.0 documentation ．

動作例

In [1]: from sympy.ntheory import factorint

In [2]: factorint(100)
Out[2]: {2: 2, 5: 2}

はい簡単．

実行時間について

In [7]: %time factorint(131)
CPU times: user 55 µs, sys: 4 µs, total: 59 µs
Wall time: 65.8 µs
Out[7]: {131: 1}

適当にキーボードを叩いてみて．

In [8]: %time factorint(127128574306)
CPU times: user 581 µs, sys: 0 ns, total: 581 µs
Wall time: 565 µs
Out[8]: {2: 1, 63564287153: 1}

まだいける．

In [9]: %time factorint(475646893209485734869943817574386974835048976415)
CPU times: user 5min 4s, sys: 204 ms, total: 5min 4s
Wall time: 5min 4s
Out[9]: 
{5: 1,
 151: 1,
 479: 1,
 1024775561: 1,
 1555754843799829: 1,
 824958834555644183: 1}

時間かかる． もうやめておこう．

しっかりと素因数分解してくれるので使えるやつですね．