약혼수(Betrothed Number)란?
약혼수(Betrothed Number)는 수론에서 다루는 흥미로운 개념으로, 한 수의 진약수(자기 자신을 제외한 약수)의 합이 상대 수보다 정확히 1만큼 큰 두 수의 쌍을 가리킵니다. 조건을 식으로 표현하면 다음과 같습니다.
- A의 진약수의 합 = B + 1
- B의 진약수의 합 = A + 1
가장 잘 알려진 예시는 (48, 75)입니다.
- 48의 진약수: {1, 2, 3, 4, 6, 8, 12, 16, 24} → 합계 76 (= 75 + 1)
- 75의 진약수: {1, 3, 5, 15, 25} → 합계 49 (= 48 + 1)
두 수가 마치 서로 짝을 이루는 것처럼 관계를 맺고 있다고 해서 '약혼수'라는 이름이 붙었습니다. 참고로 약혼수는 준친화수(quasi-amicable number)라고도 불리며, 처음 몇 개의 쌍은 (48, 75), (140, 195), (1050, 1925), (1575, 1648) 등이 있습니다.
알고리즘 설계
1부터 n 사이의 모든 약혼수 쌍을 찾으려면 다음 절차를 따릅니다.
- 범위 내의 각 수 num에 대해, 2부터 √num까지 나누어 떨어지는 수를 찾아 진약수의 합(sum)을 구합니다. 이때 i × i = num인 경우 같은 약수를 두 번 더하지 않도록 주의합니다.
- sum이 num보다 크면, num2 = sum − 1을 짝 후보로 삼습니다.
- num2의 진약수의 합(sum2)을 같은 방식으로 계산합니다.
- sum2가 정확히 num + 1과 일치하면 (num, num2)는 약혼수 쌍이므로 출력합니다.
C++ 구현 코드
#include <iostream>
using namespace std;
void BetrothedPairs(int n) {
for (int num = 1; num < n; num++) {
int sum = 1;
// 2부터 제곱근까지 검사하여 진약수의 합을 구함
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
sum += i;
if (i * i != num) // 완전제곱수일 때 중복 합산 방지
sum += num / i;
}
}
if (sum > num) {
int num2 = sum - 1;
int sum2 = 1;
for (int j = 2; j * j <= num2; j++) {
if (num2 % j == 0) {
sum2 += j;
if (j * j != num2)
sum2 += num2 / j;
}
}
if (sum2 == num + 1)
cout << "(" << num << ", " << num2 << ")" << endl;
}
}
}
int main() {
int n = 5000;
BetrothedPairs(n);
}
실행 결과
n = 5000까지 탐색하면 다음 세 쌍의 약혼수가 출력됩니다.
(48, 75) (140, 195) (1050, 1925)
시간 복잡도
약수를 구할 때 제곱근까지만 검사하므로 하나의 수에 대한 약수 합 계산은 O(√n)입니다. n개의 수를 모두 확인해야 하므로 전체 시간 복잡도는 O(n√n)이 됩니다. n이 매우 커지는 경우에는 에라토스테네스의 체를 응용해 여러 수의 약수 합을 한 번에 미리 계산하는 방식으로 성능을 개선할 수 있습니다.