Số Betrothed (cặp số bạn bè) trong C

Cặp số Betrothed: tổng ước số thực của số này = số kia + 1. Ví dụ (48, 75): ước 48 tổng 76, ước 75 tổng 49.

Thuật toán

BetrothedPairs(n)
    VỚI num = 1 ĐẾN n
        TÍNH TỔNG ƯỚC THỰC sum
        NẾU sum > num
            num2 = sum - 1
            TÍNH TỔNG ƯỚC THỰC sum2 CỦA num2
            NẾU sum2 == num + 1 THÌ IN (num, num2)
KẾT THÚC

Chương trình C++ 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++) {
            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() { BetrothedPairs(5000); }

Kết quả

(48, 75)
(140, 195)
(1050, 1925)
(1575, 1648)
(2024, 2295)
(5775, 6128)