[Algorithm] 최대공약수

최대공약수

-정수들의 공통된 약수중 가장 큰 약수

 

방법1: 전체 순회

1) 정수들 중 가장 작은 정수를 찾눈다

2) 정수의 값을 하나씩 줄여 나가면서(i) 두 정수를 나눈다

3) 둘 다 0으로 나누어 떨어질 때의 i 가 최대공약수가 된다

N, M = map(int, input().split())
lst = []

minimum = min(N,M)

for i in range(1,minimum+1):
    if (N % i == 0) and (M % i == 0):
        lst.append(i)
    else: 
        continue

print(lst[-1])

 

방법 2 : 유클리드 알고리즘

- a>b, a와 b의 최대공약수는 b와 a%b와 같다 (gcd(a, b) == gcd(b, a%b))

1) 정수 두개 중 작은값을 찾는다

2) 큰 값을 작은 값으로 나눈 나머지가 0이 될 때 까지 반복 (while b == 0)

• a = b
• b = a%b

3) while 종료 후 a 값 == 정수 a, b의 최대공약수

def euclidian_gcd(num1, num2):
    a = max(num1, num2)
    b = min(num1, num2)
    while b != 0:
    	a = b
        b = a%b
    return a

 

++ 유클리드 알고리즘을 사용하여 두 정수의 최소공배수 구하기

• (num1*num2)//두 수의 최대공약수