【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の各数で割り切れる最小の正数になります。

さいごに

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

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

以上、コジマでした。


Pythonカテゴリの最新記事