Algorithm - GCD (유클리드 알고리즘)

• gcd(a,b): (단, a가 b보다 커야 한다.)
• if b==0: return a
• return gcd(b,a%b)

• a*b=gcd*최소공배수 이기 때문에, 최소공배수는 a*b/gcd(a,b)이다.

GCD

1. 임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정한다.

2. a를 b로 나눈 나머지를 n 이라고 하면(a%b = n), n이 0일때, b가 최대 공약수(GCD).

3. 만약 n이 0이 아니라면, a에 b값을 다시 넣고 n를 b에 대입 한 후 다시 위에 step2부터 반복한다.

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

여러 숫자들의 최대공약수

1. 3개 이상의 수들에 대한 최대공약수를 구하고 싶으면, gcd를 모든 원소에 적용한다.

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

arrays=[18,30,102,105]
division=gcd(array[0],array[1])
for i in array[1:]:
    division=gcd(i,division)
return division

최소공배수

• a*b=gcd*최소공배수 이기 때문에, 최소공배수는 a*b/gcd(a,b)이다.