Ở đây chúng ta sẽ thấy số Betrothed. Đây là một cặp số, sao cho tổng các ước số thích hợp của một số lớn hơn một số khác. Chúng ta phải tìm những cặp này
Ví dụ, cặp này giống như (48, 75). Vậy các ước của 48 là {1, 2, 3, 4, 6, 8, 12, 16, 24} và tổng là 76. Tương tự, các ước của 75 là {1, 3, 5, 15, 25} nên tổng là 49.
Thuật toán
BetrothedPairs (n) -
begin for num in range 1 to n, do sum := 1 for i in range 2 to num, do if num is divisible by i, then sum := sum + i if i * i is not same as num, then sum := sum + num / i end if end if if sum > num, then num2 := sum – 1 sum2 := 1 for j in range 2 to num2, do if num2 is divisible by j, then sum2 := sum2 + j if j * j is not same as num2, then sum2 := sum2 + num2 / j end if end if done if sum2 = num + 1, then print the pair num and num2 end if end if done done end
Ví dụ
#include <iostream> using namespace std; void BetrothedPairs(int n) { for (int num = 1; num < n; num++) { int sum = 1; for (int i = 2; i * i <= num; i++) { //go through each number to get proper divisor if (num % i == 0) { sum += i; if (i * i != num) //avoid to include same divisor twice 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); }
Đầu ra
1