【Project Euler】No5 : Smallest multiple 解答例【Python】

【Project Euler】No5 : Smallest multiple 解答例【Python】

はじめに

コジマです。

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

問題

問題5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

和訳(意訳)
2520は1から10の各数で割り切れる最小の数である。

1から20の各数で割り切れる最小の正数を求めよ。

解答例

素因数分解には一意性というのがありまして、
1を除いた2〜20までの自然数を素因数だけで組み合わせて作れるパターンを考えればいいです。

素因数分解してみると
2=>2
3=>3
4=>2^2
5=>5
6=>2*3
7=>7
8=>2^3
9=>3^2
10=>2*5
11=>11
12=>2^2*3
13=>13
14=>2*7
15=>3*5
16=>2^4
17=>17
18=>2*3^2
19=>19
20=>2^2*5

となって、
2が4個、3が2個、5、7、11、13、17、19が1個あればよくて、それらを掛け合わせた数字が題意を満たす、すなわち1から20の各数で割り切れる最小の正数になります。

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

# 素因数が20までの間に何個あればよいか
# 調べれば良い

#探索のための数を初期化
num = 20
#素数を初期化
pf_array = [2, 3, 5, 7]

# 2桁以上の素数判定
for n in range(10, num + 1):
    # 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))+1, 2):
        if(n % i == 0):
            # 素数じゃない
            continue

    # 素数
    pf_array.append(n)

print(pf_array)

# 素因数探す
min_multiple = 1
for i in pf_array:
    j = 1
    # numを超えるまでかける
    while i ** j <= num:
        min_multiple *= i
        j += 1

# この式に等しくなる
# print((2**4)*(3**2)*5*7*11*13*17*19)
print(min_multiple)

さいごに

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

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

もっと学びたい人はこちら

Python、機械学習をもっと学びたいという人のためにおすすめのUdemy講座を紹介いたします!

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

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

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

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

以上、コジマでした。


Pythonカテゴリの最新記事