Skip main navigation

Euclid’s Algorithm/ユークリッドのアルゴリズム(ユークリッドの互除法)

Euclid's Algorithm/ユークリッドのアルゴリズム(ユークリッドの互除法)
© Keio University
私たちに必要なのは、2つの数字の最大公約数を見つける方法です。

もしかすると、皆さんはすでに小学校の頃に、基本的な考え方は学んだかもしれません。例えば、 (20 = 5times 4)、(15 = 5times 3)であり、20と15の最大公約数は5となります。しかし、問題のサイズが大きくなったときにどのくらい大変な問題であるのかを今一度認識しなくてはなりません。この場合そこまで難しい問題ではありませんが、どのように行うかを学ぶことは非常に有意義です。

Euclid(ユークリッド)は、幾何学への偉大な功績により、古代ギリシアの数学者の中で最も有名であり、減算の繰り返しによる最大公約数を発見するアルゴリズムも発見しています。このユークリッドのアルゴリズムを、126と72の最小公倍数の例を通して見てみましょう。まず以下のように、大きな数字から、小さな数字を順番に引いていきます。

(126 – 72 = 54)
(72 – 54 = 18)
(54 – 18 = 36)
(36 – 18 = 18)
(18 – 18 = 0)

そして、最後の0でない値が、最大公約数となります。(126 = 7times 18)と、(72 = 4times 18)のようになります。そのため(mathrm{gcd}(126,72) = 18)と書くことができます。途中で (54 = 3times 18)とすぐ気がつくかもしれませんが、その場合数ステップ早く計算を終わらせることができます。

ユークリッドのアルゴリズムは、美しく視覚化することができます。(mathrm{gcd}(x,y))を見つけるために、(xtimes y)の四角形を作ります。そして、その四角形を入りうるる最も大きな正方形(1つもしくは複数の、辺の長さが(x)と (y)の小さい方の正方形)で埋めていきます。

このアルゴリズムは最初の週で説明したような、計算複雑性という観点から効果的で、桁の大きさに関して多項式時間的な時間増加で解くことが可能です。

© Keio University
This article is from the free online

量子コンピュータ入門

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education