【Project Euler】Problem 3: 最大の素因数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 ３： 最大の素因数

原文 Problem 3 Largest prime factor

問題の要約：600851475143の最大の素因数を求めよ

本来は素数を生成するプログラムから書くところなのでしょうが、ちょっと安易にsympyのnextprimeを使って書きました。このnextprimeは使い勝手が良いので覚えておくと便利だと思います。

from sympy import nextprime 

N = N1 = 600851475143
p = 1
while N1 > 1:
  p = nextprime(p)
  if N1 % p == 0:
    N1 //= p
print(f"Answer : {p}")

さらに楽をするのであればfactorintを使えば一発です。

from sympy import factorint

print(list(factorint(600851475143).keys())[-1])

（開発環境：Google Colab）