Output練習のためProjectEulerを解いてみる第3問目です。
それでは解いていきます。

#3 Largest Prime Factor

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の最も大きい素因数は何か？

方針

ある数の素因数を求めるということなので、1~Nまでの素数をエラトステネスの篩で求めてあげて、600851475143を素数で割って素因数を求めました。

解法1

ProjectEuler_3.py

N = 600851475143
def divisor_generate(NUM):
    divisor = {n for n in range(2, NUM + 1)}
    for i in range(2, int(NUM**0.5)+1):
        for j in range(2*i, NUM+1, i):
            divisor.discard(j)
    return divisor

divisor = divisor_generate(int(N**0.5))
factor = []
for d in divisor:
    if N % d == 0:
        factor.append(d)
print(max(factor))

これを解くと4613732が得られる。
ここで使っているテクニックとして、集合の要素を削除するときに、discardを使うことでない数字が代入されてもエラーを起こさないようにしています。また、今回は素数で一回割れたらfactorに挿入する方法をとっているので、$600851475143 = a^2 \times b \times c^4 ...$という可能性もありましたが、求められているものは最も大きい素因数なので、あえて除外しました。