ตรวจสอบ Number แสดงเป็นผลรวม 2 Abundant Numbers ใน C++

สมมติมี Number ต้องการแสดงเป็นผลรวม 2 Abundant Numbers ถ้าได้พิมพ์ตัวเลข มิฉะนั้น -1 Abundant Number คือ Number ที่ผลรวม Proper Divisors (sum(n)) มากกว่าตัวเลขเอง

วิธีแก้: เก็บ Abundant Numbers ทั้งหมดใน Set สำหรับ Number n วน Loop i=1 ถึง n ตรวจสอบ i และ (n-i) เป็น Abundant หรือไม่

ตัวอย่างโค้ด C++

#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);
}

ผลลัพธ์

12 18