Tổng Aliquot (Aliquot Sum) trong C++

Tổng Aliquot của n là tổng tất cả ước số thực sự (proper divisors) của n, tức là các ước trừ chính n.

Ví dụ

n = 20. Ước: 1, 2, 4, 5, 10, 20. Aliquot sum = 1+2+4+5+10 = 22.

Số hoàn hảo (Perfect Number)

Nếu Aliquot sum = n → n là số hoàn hảo. Ví dụ: 6 (1+2+3=6), 28 (1+2+4+7+14=28), 496, 8128.

Thuật toán

getAliquotSum(n):
    sum = 0
    for i = 1 to n-1:
        if n % i == 0: sum += i
    return sum
end

Code cơ bản O(n)

#include <iostream>
using namespace std;

int getAliquotSum(int n) {
    int sum = 0;
    for(int i = 1; i < n; i++)
        if (n % i == 0) sum += i;
    return sum;
}

int main() {
    int n;
    cout << "Nhap so: ";
    cin >> n;
    cout << "Aliquot sum cua " << n << " la " << getAliquotSum(n);
    return 0;
}

Kết quả

Nhap so: 20
Aliquot sum cua 20 la 22

Tối ưu O(√n)

int getAliquotSumFast(int n) {
    if (n <= 1) return 0;
    int sum = 1; // 1 luôn là ước
    
    for(int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) // Tránh cộng 2 lần cho số chính phương
                sum += n / i;
        }
    }
    return sum;
}

Chuỗi Aliquot (Aliquot Sequence)

Lặp lại Aliquot sum: s₀ = n, sₖ₊₁ = aliquot(sₖ).

• Kết thúc ở 0 → số deficient/abundant.
• Lặp lại (cycle) → amicable numbers (cặp) hoặc sociable numbers (chuỗi).
• Ví dụ cặp amicable: (220, 284).

Code tìm cặp amicable

void findAmicable(int limit) {
    vector<int> aliquot(limit + 1);
    for(int i = 1; i <= limit; i++)
        aliquot[i] = getAliquotSumFast(i);
    
    for(int i = 2; i <= limit; i++) {
        int j = aliquot[i];
        if (j > i && j <= limit && aliquot[j] == i)
            cout << "Amicable pair: " << i << " " << j << endl;
    }
}