[ Python ] 최대공약수 구하기 프로그램

사용자로부터 두 수를 입력 받아 유클리드 알고리즘을 이용해 최대공약수를 구하는 프로그램 작성해보자.

 

n = int(input("정수1 입력: "))
m = int(input("정수2 입력: "))

if n < m:
    n,m = m,n

while m > 0:
    r = n % m
    n,m = m,r

if n != 1:
    print("두 수의 최대공약수: ", n)
else:
    print("두 수는 서로소이다.")

 

결과값 출력 모습

 

결과값 출력 모습

 

▶️ 유클리드 호제법

a와 b를 자연수라고 하고 a를 b로 나눈 나머지를 r이라고 하면 → (a,b) = (b,r)

722 % 190 = 3 나머지 152
190 % 152 = 1 나머지 38
152 % 38 = 4 나머지 0

따라서 722와 190의 최대공약수는 나머지가 0이 되는 38이다.

 

▶️ n과 m을 나눌 때, n이 더 작은 경우는 n과 m의 순서를 변경함

if n < m:
    n,m = m,n

 

▶️ n값이 1이 아닐 때는 계산된 두 수의 최대공약수를 출력하고, n의 값이 1일 경우에는 두 수가 서로소임을 출력함

if n != 1:
    print("두 수의 최대공약수: ", n)
else:
    print("두 수는 서로소이다.")