[C++]프로젝트 오일러 23번 문제&풀이 (두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?)

문제 23번

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 과잉수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 과잉수 중에서는 가장 작습니다.
따라서 과잉수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 과잉수의 합으로 표현 가능함을 보일 수가 있습니다.
두 과잉수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 과잉수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

 

접근방법

1. 완전수를 판별하는 함수 코드(calSum)를 21번 문제의 코드에서 그대로 가지고 왔다.

2. 벡터(ab_vec)에 28123 이하의 과잉수를 전부 담는다.

3. 벡터(num_vec)에 1부터 28123까지의 숫자를 전부 담는다.

4. 벡터(ab_vec)에서 각 요소의 합이 28123 이하이면, 벡터(num_vec)의 요소 중 같은 값이 있는지 확인하고, 그 값을 0으로 변경해준다.

5. 벡터(num_vec)의 모든 요소의 합을 구해주면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int calSum(int num)
{
    if (num == 1)
        return 0;
    else
    {
        vector<int> vec;

        int n = 2;
        int sum = 0;

        vec.clear();
        vec.push_back(1);

        for (int n = 2; n <= (num / 2); n++)
        {
            if (num % n == 0)
            {
                vec.push_back(n);
                vec.push_back(num / n);
            }
        }

        for (int i = 0; i < (int)((vec.size() / 2) + 1); i++)
        {
            sum += vec[i];
        }

        return sum;
    }
}

int main()
{
    vector<int> ab_vec;

    for (int n = 1; n <= 28123; n++)
    {
        if (calSum(n) > n) ab_vec.push_back(n);
    }

    vector<int> num_vec;

    for (int n = 0; n < 28123; n++)
    {
        num_vec.push_back(n + 1);
    }

    for (int i = 0; i < ab_vec.size(); i++)
    {
        for (int j = i; j < ab_vec.size(); j++)
        {
            if (ab_vec[i] + ab_vec[j] <= 28123)
            {
                for (int n = 0; n < num_vec.size(); n++)
                {
                    if (num_vec[n] == ab_vec[i] + ab_vec[j])
                    {
                        num_vec[n] = 0;
                    }
                }
            }
        }
    }

    int sum = 0;

    for (int k = 0; k < num_vec.size(); k++)
    {
        //cout << num_vec[k] << endl;
        sum += num_vec[k];
    }

    //cout << endl;
    cout << "Answer is : " << sum << endl;

    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler