砂場で遊ぼう

c++/python/mathematica などの練習帳

Project Euler 003 / 最大の素因数(Largest prime factor)

問題概略

600851475143 の素因数の中で最大のものを求めよ。

https://projecteuler.net/problem=3

factorintで素因数分解

sympy の factorint で素因数分解します。

sympy.factorint(600851475143) の結果は「素数:指数」の辞書で,キーである素数は小さいものから順に並んでいます。

 \{71: 1,\, 839: 1,\, 1471: 1,\, 6857: 1\}

一番最後の要素のキーが答えです。reversed で逆順にして,next で先頭のキーを取得しました。

    import sympy

    print(next(reversed(sympy.factorint(600851475143))))