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

done is better than perfect

自分が学んだことや、作成したプログラムの記事を書きます。

project euler problem3

project euler3問目

13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ.

少し工夫が必要な問題です。単純に数値を1から順番に割っていくような方法では多分終わらないでしょう

number = 600851475143
i = 3
factors = []
product = 1

while True:
    if number % i == 0:
        factors.append(i)
        product *= i
        number /= i
        if product >= number:
            break
    i += 2

print factors
print number