Python으로 두 숫자의 공약수 구하기 – 초보자를 위한 완벽 가이드

이 글에서는 두 숫자의 공약수(공통 약수)를 구하는 파이썬 프로그램에 대해 자세히 알아보겠습니다.

문제 정의

문제: 두 개의 정수가 주어졌을 때, 두 수의 공약수를 모두 찾아야 합니다.

예를 들어 5와 45가 주어지면, 두 수를 모두 나누어 떨어지게 하는 수는 1과 5이므로 공약수는 총 2개입니다.

접근 방법

가장 직관적인 방법은 다음과 같습니다.

1. 입력받은 두 수 중 더 작은 값을 구합니다. (min() 함수 활용)
2. 1부터 그 최솟값까지 차례대로 반복하면서, 각 값이 두 수를 모두 나누어 떨어지게 하는지 확인합니다.
3. 조건이 참일 때마다 카운터(counter)를 1씩 증가시켜 공약수의 개수를 셉니다.

두 수 중 작은 값까지만 확인하면 되는 이유는, 큰 값보다 큰 수가 작은 수의 약수가 될 수 없기 때문입니다. 이렇게 하면 불필요한 연산을 줄여 효율성을 높일 수 있습니다.

예제 코드

a = 5
b = 45
count = 0
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        count += 1
print(count)

출력 결과

2

코드 동작 원리

위 예제의 실행 과정을 단계별로 살펴보겠습니다.

1. min(5, 45) → 두 수 중 작은 값인 5를 구합니다.
2. range(1, 6) → 1부터 5까지 반복합니다.
3. i = 1: 5 % 1 == 0, 45 % 1 == 0 → 조건 참, count = 1
4. i = 5: 5 % 5 == 0, 45 % 5 == 0 → 조건 참, count = 2
5. 반복 종료 후 최종 결과 2를 출력합니다.

모든 변수는 지역 범위(local scope) 내에서 선언되며, 반복문 안에서만 참조됩니다.

참고: 공약수 목록 자체를 출력하고 싶다면?

개수가 아니라 공약수 목록이 필요하다면 리스트에 값을 담아 출력할 수 있습니다.

a = 5
b = 45
divisors = [i for i in range(1, min(a, b)+1) if a % i == 0 and b % i == 0]
print(divisors)   # [1, 5]
print(len(divisors))  # 2

마무리

이 글에서는 파이썬으로 두 숫자의 공약수를 찾는 방법을 배웠습니다. min() 함수와 반복문만으로도 간단하게 구현할 수 있으며, 필요에 따라 공약수의 개수 또는 목록 자체를 출력하도록 응용할 수 있습니다.

더 나아가 최대공약수(GCD)만 필요하다면 파이썬 표준 라이브러리의 math.gcd() 함수를 사용하는 것도 좋은 선택입니다.