Kiểm tra số biểu diễn được thành tổng hai số dồi dào (abundant) trong C++

Cho số n, biểu diễn dưới dạng tổng của hai số dồi dào (abundant number). Số dồi dào: tổng ước số thực sự > số đó. Nếu không thể, in -1.

Cách: sinh tập hợp các số dồi dào đến N. Với n cho trước, duyệt i từ 1 đến n, kiểm tra i và n-i đều có trong tập hợp.

Ví dụ

#include <iostream>
#include <set>
#define N 100005
using namespace std;

set<int> getAbundantSet() {
    set<int> abundant_set;
    for (int i = 1; i < N; i++) {
        int sum = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                sum += j;
                if (i / j != j)
                    sum += i / j;
            }
        }
        if (sum > i)
            abundant_set.insert(i);
    }
    return abundant_set;
}

void representSumAbundant(int number){
    set<int> abundant_set = getAbundantSet();
    for (int i = 1; i <= number; i++) {
        if (abundant_set.count(i) && abundant_set.count(number - i)) {
            cout << i << " " << number - i;
            return;
        }
    }
    cout << -1;
}

int main() {
    int n = 30;
    representSumAbundant(n);
}

Kết quả

12 18