[アルゴリズム]白準2609号最大公倍数と最小公倍数(Python)

白駿#2609
問題のショートカット
質問する
:プログラムを作成し、2つの自然数を入力し、最大公約数と最小公約数を出力します.
I/Oルール
1.入力

行目は2つの自然数を与える.この2つは10000以下の自然数で、真ん中にスペースがあります.
2.出力

第1行は、与えられた2つの数の最大公倍数を出力し、第2行は、与えられた2つの数の最小公倍数を出力する.

質問へのアクセス
与えられた2つの数を入力値として最大公約数と最小公約数を出力する問題.対応する値はユークリッドアーク法により容易に求めることができる.mathモジュールには最大公約数(gcd)と最小公倍数(lcm)を求める関数があるが,ユークリッドアーク除去法に基づいて解いた.
問題解決(Python)

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
        
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

かいがく
最大公倍数と最小公倍数
最大公約数は?同時に彼らのすべての約数整数であり、約数の中で最大の数である.
最小公倍数はいくらですか.最小公倍数は、正の公倍数の中で最小です.
ユークリッドアークほう
ユークリッドアーク除去法は、2つの自然数または整数の最大公因数を求めるアルゴリズムの1つであり、アーク除去法は、2つの数が互いに相手数で除算され、最終的に必要な数が得られるアルゴリズムを指す.
2つの自然数(または整数)a、bについて、aをbで割った残りの数がr(ただし、a>b)である場合、aおよびbの最大公約数(gcd)はbおよびrの最大公約数に等しい.この性質に基づいて、bをrの残りのr’で割って、rをr’の残りの過程で割って、残りが0の時、除いた数はaとbの最大公約数です.

最大公約数GCD

最小公倍数LCM(Least Common Multiple)