読者です 読者をやめる 読者になる 読者になる

Problem 3 - Project Euler

PE python

600851475143 の素因数のうち最大のものを求めよ。

大きすぎる数値

素数のリストが作れてしまえば簡単なんですが、昨日も書いたように数値が大きすぎてlong型になってしまいます。xrangeはlong型は扱えないみたい(int型に変換しようとするっぽい)なのです。python 3 ならとも思ったんですが、これもメモリエラー。

ちょっとズルしてみた

まず、600851475143という数字は奇数ですので、素因数は少なくとも3以上になります。そうすると、素因数で最も大きな数は600851475143の3乗根以下になるはずです。(追記)何を寝ぼけてたか知りませんが、3乗根ではなく3分の1が正解ですね。失礼しました。

n乗根を求めるにはmathモジュールのpow関数を使用します。

import math
math.pow(600851475143, (1.0/3.0)) # 8438.3145557747084

これで素因数は8439より小さい事がわかりました。(追記)上にも書きましたが、これは間違いです。

素数のリストは素数のリストを生成する(エラトステネスの篩) - kk6のメモ帳*を利用して求めます。

p = Eratos(8439)
p.search_prime()
[i for i in p.prime if 600851475143 % i == 0]
[71, 839, 1471, 6857] #600851475143 の素因数のうち最大のものは6857

なんとか解けましたが

問題が問題なので「600851475143 は素数ではない」という仮定の下なんとか解けましたが、そもそもが自作の素数リストを生成するコードがダメみたいですね...orz