수학 알고리즘 - 최대 공약수

최대 공약수

최대공약수는 핵심포인트는 두 개 이상의 정수를 나누어 떨어지게 하는 가장 큰 양의 정수를 말한다.

최대 공약수를 구하는 데에는 여러 알고리즘이 있다.

일단 그냥 단순히 푸는 방법을 생각해보자. 가장 작은 수를 시작으로 두 개의 수 모두 딱 떨어지게 나눌 수 있는 수를 찾는 것이다.

## 최대공약수

def find_greatest_common_factor(n,m):
    small_number = min(n,m)
    big_num = max(n,m)

    i = big_num
    while i > 1: #
        if big_num % i == 0 and small_number % i == 0:
            return i
        i -= 1

    return 1

print(find_greatest_common_factor(17,19))
print(find_greatest_common_factor(9,18))
print(find_greatest_common_factor(1,19))

그런데!

만약 입력값이 0이 된다면 0이 아닌 다른 수가 최대 공약수가 된다. 그 부분을 추가해주자.

## 최대공약수

def find_greatest_common_factor(n,m):
    if n == 0 or m == 0:
        return max(n,m)
    small_number = min(n,m)
    big_num = max(n,m)

    i = big_num
    while i > 1: #
        if big_num % i == 0 and small_number % i == 0:
            return i
        i -= 1

    return 1

print(find_greatest_common_factor(17,19))
print(find_greatest_common_factor(9,18))
print(find_greatest_common_factor(1,19))
print(find_greatest_common_factor(0,19))
print(find_greatest_common_factor(0,0))