[Python][Julia]Project euler3 (プロジェクトオイラー3)

Project euler Ploblem 3 (プロジェクトオイラー3)

Largest Prime Factor

備忘のために残しておく。

2023/12/29 コメントで指摘の通り、誤ったコードを書いていたので修正しました。
（コメントありがとうございます)

問題文

13195の素因数は5,7,13,29である。
600851475143の最大の素因数は？

(原文)
The prime factors of 13195 are 5,7,13 and 29.
What is the largest prime factor of the number 600851475143?

解答

答え

6857

解答の方針

求める値の平方数までの素因数を前から順にリストに追加する。
例えば、12の場合だと[3,2]、25の場合だと[5]。
今回の場合は、[6857, 1471, 839, 71]
リストの一番前が、最大の素因数となる。
素数の判定アルゴリズムに「エラトステネスの篩」があるが、今回は使用しなかった
参考：エラトステネスの篩

Pythonのコード

Python(Ploblem3)

def largest_prime_factor(num: int) -> int:
    divisor =[]
    temp = num
    for i in range(2, int(num**0.5) + 1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            divisor.insert(0,i)
    if temp != 1:
        divisor.insert(0,temp)
    if divisor == []:
        divisor.insert(0,temp)
    return divisor[0]

num = 600851475143
print(largest_prime_factor(num))

Juliaのコード

Julia(Ploblem3)

function largest_prime_factor(num::Int64)::Int64
    temp = num
    divisor = []
    for i in 2:ceil(num^0.5)
        if temp % i == 0
            while temp % i == 0
                temp ÷= i
            end
            insert!(divisor, 1, i)
        end
    end
    if temp != 1
        insert!(divisor, 1, temp)
    end
    if divisor == []
        insert!(divisor, 1, temp)
    end
    return divisor[1]
end
num = 600851475143
println(largest_prime_factor(num))