[오일러 프로젝트 23] 두 초과수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

해당 문제의 경우 boolean 배열 통해서 초과수를 저장해 두는 것이 효율적이다. 동적 배열에 무식하게 초과수를 넣어두기 시작하면 다시 찾아야하는 오버헤드가 발생한다!

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool bignumTable[28200];

bool isBignum(int n) {
    int divisorSum = 0;
    for (int i = 1; i < n - 1; i++) {
        if (n % i == 0) divisorSum += i;
    }
    if (divisorSum > n) {
        return true;
    }
    else {
        return false;
    }
}

int main() {

    // 1 - 28123 까지의 초과수를 구한다.
    for (int i = 1; i <= 28123; i++) {
        if (isBignum(i)) {
            bignumTable[i] = true;
        }
    }
    
    // 1 - 28123 까지 초과수 두개의 합으로 나타낼 수 없는 정수를 구한다.
    int answer = 0;
    for (int i = 1; i <= 28123; i++) {
        if (i <= 12) {
            answer += i;
        }
        else {
            for (int idx = 1; idx < 28200; idx++) {
                if (i - idx <= 0) {
                    answer += i;
                    break;
                }
                else {
                    if (bignumTable[i - idx] && bignumTable[idx]) break;
                }
            }
        }
    }

    cout << answer << endl;

    return 0;
}

 

초과수를 계산하는 부분을 최적화하면 좀 더 빠른시간안에 계산이 가능하다. 약수에 관련한 최적화 방법을 다시 공부해봐야겠다.