【Project Euler】No3: Largest prime factor 解答例【Python】

【Project Euler】No3:	Largest prime factor 解答例【Python】

はじめに

コジマです。

https://projecteuler.net/
の3問目を解いていきます。

問題

問題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の最大の素因数はなんでしょう ?

解答例

素数の問題では
【Python】素数判定の計算量を減らしていく【数学】
この記事で使った手法を使っていきます。
これからたくさん登場します。

# おまじない
import numpy as np
import math

# 問題の数
num = 600851475143
#探索のための数を初期化
n = 2
#素因数を初期化
pf = 2

while n:
    n+=1
    # 素数か判定する
    # 1桁は決め打っちゃう
    if n in [2,3,5,7] and n < 10:
        pf = n
    # 素数じゃない一桁
    elif n < 10:
        continue
    # 2桁以上は別ロジックで
    else:
        # 1の位が [0, 2, 4, 5, 6, 8]の時計算不要
        if n % 10 in [0, 2, 4, 5, 6, 8]:
            # 素数じゃない
            continue

        # 3の倍数判定
        # 1文字ずつの配列作成
        num_array = list(map(int, str(n)))
        if sum(num_array) % 3 == 0:
            # 素数じゃない
            continue
        
        # √nまで調べればOK
        for i in range(3 , int(math.sqrt(n)), 2):
            if(n % i == 0):
                # 素数じゃない
                continue
        
        # 素数
        pf = n
    
    # 割り切れるか
    if num % pf == 0:
        print("素因数は: {}".format(pf))
        num = num / pf
        
        # numを1にした素数が最大素数
        if num == 1:
            print("最大素因数は: {}".format(pf))
            break
    else:
        # 割り切れない(素因数じゃない)
        continue

さいごに

解答はgithubにも上げています。
https://github.com/kojimanotech/project_euler/blob/master/0003_Largest_prime_factor.ipynb

この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです!

以上、コジマでした。


Pythonカテゴリの最新記事