Pythonで実装するユークリッドの互除法　最大公約数の計算

最大公約数：ユークリッドの互除法

整数A,B間の最大公約数(Greatest Common Divisor : GCD)は「ユークリッドの互除法」で求めることができます。下記はpythonでの実装例です。

a,b=map(int,input().split())
A=max(a,b)
B=min(a,b)
tmp=0
while A%B!=0:
	tmp=B
	B=A%B
	A=tmp
print(B)

A,B間の最小公倍数(Least Common Multiple : LCM)は最大公約数(GCD)を使って下記のように求めることができます。

LCM=（A*B）/ GCD(A,B)

AとBをかけて、AとBの最大公約数で割れば求めることができます。
Pythonでの実装例は下記のとおりです。

a,b=map(int,input().split())
A=max(a,b)
B=min(a,b)
tmp=0
while A%B!=0:
	tmp=B
	B=A%B
	A=tmp
GCD=B
print((a*b)//GCD)