Tweet

Pocket

[py]
# Problem 3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

def isprime(n): # 素数判定関数
    if n < 2:
        return 0
    elif n == 2:
        return 1
    elif n % 2 == 0:
        return 0
    elif n == 3:
        return 1
    elif n == 5:
        return 1
    elif n == 7:
        return 1
    else:
        a = 3
        while a * a <= n: #a が sqrt(x) を超えるまで探索
            if n % a == 0:
                return 0
            else:
                a += 2
    return 1

x = 600851475143    # given number
ans = 0             # answer
i = 3               # prime factor

# x = 28 のとき (x,ans) = (28,0)->(14,2)->(7,2)->(1,7) 的なアルゴリズム

while x % 2 == 0:   # 2 で割るときは別処理
    if x % 2 == 0:
        x /= 2
        ans = 2

while True:
    if x == 1:
        break
    if x % i == 0 and isprime(i) == 1:
        x /= i
        if ans < i:
            ans = i
    i += 2

print(ans)
[/py]

[py]

6857

[/py]

コメント

素数判定関数を作るのに手間取った。もっと良いやり方がありそう。

解答 pdf によると、素数の性質を使えばもっと効率的に書けるらしい。