[C++]프로젝트 오일러 21번 문제&풀이 (10000 이하 모든 친화수(우애수)의 합은?)

문제 21번

n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.

예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.

10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.

 

접근방법

1. 자신을 제외한 약수들의 합을 구하는 함수(calSum)를 만든다.

  (벡터(vec)에 약수들을 차례로 추가하고 모두 더하는 방식으로)

2. 10,000 이하의 범위에서 친화수(우애수)가 되는 수를 찾아 모두 더하면 끝!

#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()
{
    int sum = 0;

    for (int n = 2; n <= 10000; n++)
    {
        if (calSum(calSum(n)) == n && calSum(n) != n)
        {
            //cout << n << " " << calSum(n) << endl;
            sum += n;
        }
    }

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

    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler