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

はじめに

コジマです。

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

問題

問題3

解答例

素数の問題では
【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、機械学習をもっと学びたいという人のためにおすすめのUdemy講座を紹介いたします！

Pythonの基本文法を押さえたい方はこちらの動画がおすすめです。
エンジニアになりたいと思って駆け出した方がPythonを選んだときはこの講座から始めるとよいと思います。
Python 3 エンジニア認定基礎試験の対策にもなります。
はじめてのPython 少しずつ丁寧に学ぶプログラミング言語Python3のエッセンス

プログラムの基礎が分かる方で機械学習に興味がある方はこちらがおすすめです。
SIGNATEという日本版Kaggleのサービスを実際に使用してハンズオン形式でデータ分析・機械学習を学ぶことができます。
もちろんこの動画だけで特級のデータサイエンティストになれるわけではないですが、機械学習の門を叩くにはとても良い講座だと思います。
【ゼロから始めるデータ分析】 ビジネスケースで学ぶPythonデータサイエンス入門

Pythonのライブラリで必ず押さえておきたいのがNumpy, Pandas, Matplotlibの３つ。
この3つを網羅的に学ぶことができる講座です。
英語の講座ですが、わかりやすい英語ですし、ソースコードメインで解説しているので
ソースコードを一緒に手を動かしながら学べば十分理解することができます。
機械学習を使わない人にもおすすめの講座です。
2021 NumPy, Pandas and Matplotlib A-Z™: for Machine Learning

気になった人はぜひ見てみてくださいね！

以上、コジマでした。