The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
http://projecteuler.net/problem=3
600851475143の素因数の中で最大のものを見つける問題。
素因数分解は説明すれば簡単だがいざ実行すると大変な問題。
RSA暗号の安全性などで有名なので今更だが。
Sage Math にはfactor函数が用意されているので使う。
----
print max([p for p,e in factor(600851475143)])
----
リスト内包において、p for p,e in factor() という書き方は、factorという函数が素因数と指数の組を返す函数だから。素因数のみに着目するのでそのようにする。そしてリストの中から最大値を返す函数であるmax函数を使えば完成。
RSAは整数の素因数分解の難しさを利用している。
有理整数環はEuclid整域であるので同じEuclid整域である体上の多項式環でもできそうな予感がするが有理整数環とは違い簡単な方法が知られている、と聞いた覚えがある。
