プロジェクトオイラー3

プロジェクトオイラーの問題３を解いてみました。

問題
600851475143の素因数で最も大きい数字はなあに？

最初に書いたコードはこうでした。

N = int(input()) #自然数N
def primes(N): #自然数Nまでの素数のリストを作る
    prime_list = [2]
    i = 2
    while i < N + 1:
        counter = 0
        for prime in prime_list:
            if i % prime != 0:
                counter += 1
        if counter == len(prime_list):
            prime_list.append(i)
        i += 2
    return prime_list

print(primes(N)[-1])

def prime_factors(N): #自然数Mを素因数分解する(重複無視)
    factors_list = []
    for prime in primes(N): #ここまで大きく取る必要はない
        if N % prime == 0:
            factors_list.append(prime)
    return factors_list

def maximum_prime_factor(N): #自然数Nの素因数の中で最大のものを求める
    return prime_factors(N)[-1]

print(maximum_prime_factor(N))

　むっちゃ無駄が多いんですが、まあ一応合ってるはずだし答えはでるよな〜って思ってました。ところが、30分たったところでKillされました。
そこでまずはエラトステネスのふるいを実装して、次に、素数生成を必要最低限まで減らすことにしました。それでできたのがこれ

import math
N = int(input())
M = int(math.sqrt(N)) + 1

def primes(M): #エラトステネスのふるい
    prime_true_false = [1] * M
    prime_true_false[0] = 0
    prime_true_false[1] = 0
    for number in range(2, int(math.sqrt(M)) + 1):
        if prime_true_false[number]:
            for multiple in range(number * number, M, number):
                prime_true_false[multiple] = 0
    return [prime for prime in range(2, M) if prime_true_false[prime] ]

def prime_factors(N): #自然数Nを素因数分解する(重複無視)
    factors_list = []
    for prime in primes(M):
        if N % prime == 0:
            factors_list.append(prime)
    return factors_list

answer_list = prime_factors(N)

print(answer_list)
print(answer_list[-1])

N =600851475143 として1秒かからずにできたよ、ヤッタネ。