파이썬으로 두 숫자의 약수 합이 같은지 확인하는 방법

두 개의 숫자 p와 q가 주어졌을 때, 이 두 숫자의 모든 약수(제수)의 합이 서로 같은지 확인하는 문제를 풀어보겠습니다.

예를 들어 p = 559, q = 703이라고 가정해 봅시다. 559의 약수는 1, 13, 43이고, 703의 약수는 1, 19, 37입니다. 각각의 약수 합을 계산해 보면 다음과 같습니다.

• 559의 약수 합: 1 + 13 + 43 = 57
• 703의 약수 합: 1 + 19 + 37 = 57

두 합이 모두 57로 같으므로 결과는 True가 됩니다.

문제 해결 접근 방식

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

1. 약수의 합을 구하는 함수 divSum()을 정의합니다. 이 함수는 숫자 n을 입력받습니다.
2. 합계를 저장할 변수 total을 1로 초기화합니다. (1은 모든 수의 공통 약수이므로 미리 포함)
3. i를 2부터 시작하여 i * i <= n인 동안 반복합니다.
4. n이 i로 나누어 떨어지면, i와 n / i의 몫(floor)을 함께 total에 더합니다. 하나의 약수 i를 찾으면 짝이 되는 약수 n/i도 동시에 찾을 수 있기 때문입니다.
5. i를 1 증가시키며 반복을 계속합니다.
6. 반복이 끝나면 total을 반환합니다.
7. 메인 로직에서는 divSum(p)과 divSum(q)의 값이 같으면 True, 다르면 False를 반환합니다.

효율성의 핵심: 제곱근까지만 탐색

1부터 n까지 모든 수를 확인하는 대신 √n까지만 반복해도 충분합니다. 약수는 항상 쌍(i, n/i)으로 존재하기 때문에, 제곱근 이전까지의 약수만 찾으면 나머지 짝 약수는 자동으로 구해집니다. 이 덕분에 시간 복잡도를 O(n)에서 O(√n)으로 크게 줄일 수 있습니다.

예제 코드

from math import floor

def divSum(n):
    total = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            total += i + floor(n / i)
        i += 1

    return total
    
def solve(p, q):
    return divSum(p) == divSum(q)

p = 559
q = 703
print(solve(p, q))

입력

559, 703

출력

True

코드 설명

divSum() 함수는 2부터 √n까지의 수 중 n의 약수를 찾아, 해당 약수와 그 짝이 되는 약수(n // i)를 한 번에 더합니다. 초기값이 1이므로 자기 자신(n)은 제외된 약수의 합이 반환됩니다. 이후 solve() 함수에서 두 숫자에 대한 약수 합을 비교하여 최종 결과를 출력합니다.