のんびりプログラミング生活

画像処理、CG、プログラミングなどの話題を中心にのんびり記事を書きます。不定期更新。

最大公約数と最小公倍数を求めたいっ!- Python

皆さんこんにちは。
今回はPythonで最大公約数と最大公倍数を求めるプログラムを書いてみましょう。
何やそれ!?と思った方は重症ですので辱めを受けながら小学校に通うか、Google大先生に泣きついてください。このブログでは絶対に説明なんかしてあげないんだからね!


最大公約数と最小公倍数とは

2つ以上の正の整数に共通な約数(公約数)のうち最大のものを最大公約数といいます. 2つ以上の正の整数の共通な倍数(公倍数)のうち最小のものを最小公倍数といいます.

最大公約数と最小公倍数

 

約数を求める

まずは約数を求めてみることから始めてみましょう。約数というのは、

要はある数を割り切れればよいので、a % i == 0のときに約数であると判定するfor文を回せば良いですね。

# 約数を求める
def factors(a):
for i in range(1, a+1):
if a % i == 0:
print(i)

if __name__ == '__main__':
print("約数を求めます")
a = input("数字:")
a = float(a)

if a > 0 and a.is_integer():
factors(int(a))
else:
print("正の整数を入力してください")

a.is_integer()はaが整数かどうかを判定するもので、例えばaが2.5だったら浮動小数点が含まれるのでFalse、2.0ならTrueを返します。これが無い場合には2.0を2という整数として認識してくれないので必ずelseが実行されてしまいます。

実行例

約数を求めます
数字:12
1
2
3
4
6
12

 

最大公約数と最小公倍数を求める

本題。先ほどのプログラムがいるのかどうかと聞かれればいらないだろうという答えになりそうですが、約数が何なのか大体イメージできたということで有用判定しておきましょう。ね。

最小公倍数を求めるにはユークリッドの互除法を使います。これは中高生が習うはずなので理解している方も多いでしょう。

 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

ユークリッドの互除法 - Wikipedia

 

言葉にするとややこしいかもしれませんが、実際の数式やプログラムにすると至って簡単です。例として20をで割ってみましょう。

20 = 6 * 3 + 2

  3 = 1 * 2 + 1

  2 = 2 * 1 + 0

つまり20と3の最大公約数は1となります。これはユークリッドの互除法を使うまでもなく、3の約数は1と3のみで、20は3で割り切れないことを考えればすぐに1という答えが導き出されます。しかし例えば10倍の200と30になったときに同じように考えるのは少々面倒です。その場合には互除法が有効と言えるでしょう。

# 最大公約数と最小公倍数を求める
def factors(a, b):
if a < b:
a, b = b, a

r = a % b
x = a * b

# ユークリッドの互除法
while r != 0:
a = b
b = r
r = a % b

print("最大公約数は{0}, 最大公約数は{1}".format(b, int(x/b)))

if __name__ == '__main__':
a = float(input("数字1:"))
b = float(input("数字2:"))

if a > 0 and b.is_integer() and a > 0 and b.is_integer():
factors(int(a), int(b))
else:
print("正の整数を入力してください")

a,b2つの数字を入力させて、それらの最大公約数と最小公倍数を計算するプログラムです。mainについては先ほどと殆ど同じなので特に問題ないでしょう。

factors()において、まずはaとbの大きさを判定しています。これは当然20と3だった場合に3を20で割ろうとすれば互除法が成立しないからです。

最小公倍数も簡単で、a,bの積を最大公約数で割れば求まります。

実行例

数字1:20
数字2:3
最大公約数は1, 最大公約数は60

 

数字1:30
数字2:3
最大公約数は3, 最大公約数は30

 

数字1:200
数字2:30
最大公約数は10, 最大公約数は600

 

数字1:114514
数字2:1919
最大公約数は1, 最大公約数は219752366

 

あとがき

お疲れ様でした。今回の題材は偶々勉強中だった暗号化と、偶々読んでた「Pythonから始める数学入門」(オライリーさんから発売中)の両方で触れていたからです。本書についてはまだ読んでいる途中なので詳しいことは言えませんが、かなり読みやすくて(珍しく)おすすめです。

一か月以上更新無しだった本ブログですが、再びこうして記事を書いてみました。非常に楽しかったです。時間の許す限り更新したいと思っていますので(理想は週1or2)、どうかよろしくお願いいたします。それでは。