Project Euler その5

飛ばしてたProblem3を解いた。

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

訳

「13195の素因数は5と7,13と29である。600851475143の素因数の内最大の要素は何か？ 」

コード

import time

N = 600851475143

def factor(N):
    for i in range(2,1000000):
        if N%i == 0:
            print i
            break
    if N/i != 1:
        factor(N/i)

factor(N)

forじゃなくてwhileで回せば素因数がすごく大きくても対応できるかも。（遅いだろうな・・・）