読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Project Euler Problem 5

Project Euler
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?

http://projecteuler.net/problem=5

 

1から20の数で割り切れる最小の数を求める問題。

つまり、1から20の数の最小公倍数を求めればよい。

最小公倍数と最大公約数には以下の様な関係がある:

----

命題

正の整数$a,b$に対して$ \lcm(a,b), \gcd(a,b) $ をそれぞれ$a,b$の最小公倍数、最大公約数とする。このとき

a * b = \lcm(a,b) * \gcd(a,b)

なる関係が成り立つ。

----

それを踏まえたSage によるソースは以下のようになる。

----

print lcm(xrange(1,21))

----

一体何を踏まえているのか疑問が次々に湧くソースである。