[プログラマ](python)最大公約数と最小公倍数

質問する

説明する

def gcd(n,m):
    mod = m % n
    if mod != 0:
        m, n = n, mod
        return gcd(n, m)
    else:
        return n

def solution(n,m):
    return [gcd(n,m),int(m*n/gcd(n,m))]

+++

ユークリッドアークほう

ユークリッドアークほう

2個の自然数あるいは公式の最大承諾数のアルゴリズムを求めます
相互除算法とは、2つの数が相互除算によって最終的に所望の数を得るアルゴリズムである.
2つの自然数(または正式)a,bについて、aをbで割った残りの数をr(ただし、a>b)と呼ぶと、aおよびbの最大公約数はbおよびrの最大公約数に等しい.

+++

GCD、LCM（最大公倍数、最小公倍数）

* GCD(Great Common Divisor)

A,Bがあれば
A,Bを0で割って余りを求める.
GCD(B,A%B)
if A%B = 0, GCD=B
else GCD(B,A%B)

* LCM(Least Common Multiple)

(A*B)/GCD