파이썬으로 두 수의 공약수 개수 세기: 완전 가이드

두 개의 자연수 a와 b가 주어졌을 때, 두 수를 모두 나누어 떨어지게 하는 양의 정수, 즉 공약수가 몇 개인지 구하는 문제입니다.

예를 들어 입력이 a = 288, b = 240이라면, 공약수는 [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]로 총 10개이므로 출력은 10이 됩니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 결과를 저장할 변수 res를 0으로 초기화합니다.
• 1부터 gcd(a, b) + 1 범위의 각 숫자 i에 대해 반복합니다.
• i로 a를 나눈 나머지가 0이고, i로 b를 나눈 나머지도 0이라면 res를 1 증가시킵니다.
• 반복이 끝나면 res를 반환합니다.

여기서 핵심 아이디어는 공약수가 반드시 최대공약수(GCD)의 약수라는 점입니다. 따라서 1부터 min(a, b)까지 전부 확인하는 대신, gcd(a, b)까지만 검사하면 연산 횟수를 크게 줄일 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

from math import gcd

def solve(a, b):
    res = 0
    for i in range(1, gcd(a, b) + 1):
        if (a % i) == 0 and (b % i) == 0:
            res += 1
    return res

a, b = 288, 240
print(solve(a, b))

입력

a = 288, b = 240

출력

10

코드 설명

• math.gcd() 함수를 사용해 두 수의 최대공약수를 구합니다.
• 1부터 최대공약수까지의 모든 수에 대해 a와 b를 각각 나누어 나머지가 0인지 확인합니다.
• 두 조건을 모두 만족하면 그 수는 공약수이므로 카운트를 증가시킵니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(gcd(a, b))입니다. gcd(a, b)는 일반적으로 a와 b 중 작은 값보다 훨씬 작기 때문에, 단순히 1부터 min(a, b)까지 모든 수를 검사하는 방법(O(min(a, b)))보다 훨씬 효율적입니다.

마무리

이처럼 최대공약수를 활용하면 두 수의 공약수 개수를 간단하고 효율적으로 구할 수 있습니다. 이 원리는 약수 관련 다양한 알고리즘 문제의 기초가 되므로 꼭 기억해 두시길 바랍니다.