【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カテゴリの最新記事