파이썬 최대공약수 구하기

이번 시간에는 두 수의 최대공약수를 구해 보자!

 

최대 공약수란?

- 0이 아닌 두개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다.

 

예를 들어서 쉽게 이해해보자

 

두 정수 a = 12 b = 30의 최대공약수를 구해 보자

 

먼저, 12를 두 수의 곱으로 나타내면

12 = 12 * 1 = 6 * 2 = 4 * 3 이므로

12의 약수는 1, 2, 3, 4, 6, 12 가 된다

 

그 다음 30을 두 수의 곱으로 나타내면

30 = 30 * 1 = 15 * 2 = 10 * 3 = 6 * 5 이므로

30의 약수는 1, 2, 3, 5, 6, 10, 15, 30 이 된다

 

이때 12와 30의 공약수는 1, 2, 3, 6 이고

공약수 중 가장 큰 수는 6이므로 12와 30의 최대공약수는

gcd(12,30) = 6

이 된다

 

자 지금까지 최대공약수를 구하는 방법을 알아보았으니

코드로 최대공약수 만드는 법을 알아보도록 하자

 

 

def get_gcd(n1,n2):
    if(n1<n2):
        a=n1
    else:
        a=n2
    for i in range(1,a+1):
        if(n1%i==0 and n2%i==0):
            gcd=i
    return gcd

n1=int(input())
n2=int(input())
print(get_gcd(n1,n2))

 

먼저 두 정수 n1, n2를 입력받은 후

get_gcd 함수를 호출한다.

 

get_gcd 함수를 보면 먼저 n1, n2 중 큰 수를 a에 대입해주고

1부터 a까지 카운터변수 i를 1씩 증가시키며

n1과 n2가 나누어 떨어졌을 때의 i 값을 gcd에 대입해준다

반복문이 끝난 후 마지막 gcd의 값이

n1과 n2의 최대공약수의 값이 된다