scosant
12/17/2012 - 11:42 AM

projecteuler021 - amicable numbers

projecteuler021 - amicable numbers

/**
 * 
 * projecteuler021 - amicable numbers
 *
 * Let d(n) be defined as the sum of proper divisors of n (numbers
 * less than n which divide evenly into n).
 *
 * If d(a) = b and d(b) = a, where a != b, then a and b are an amicable
 * pair and each of a and b are called amicable numbers.
 *
 * For example, the proper divisors of 220 are:
 * {1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110}; therefore d(220) = 284.
 *
 * The proper divisors of 294 are:
 * {1, 2, 4, 71, 142}; so d(284) = 220.
 *
 * Evaluate the sum of all amicable numbers under 10000.
 */

#include <iostream>

// Returns the sum of proper divisors of n.
int d(int n);

int main(int argc, char* argv[]) {
    int begin = 0;
    int end = 10000;
    
    int b;
    int sum = 0;
    for (int a = begin; a <= end; a++) {
        b = d(a);
        if (a != b) {
            if (d(b) == a) {
                std::cout << a << ", " << b << std::endl;
                sum += a;
            }
        }
    }
    std::cout << "sum = " << sum;
}

int d(int n) {
    int sum = 0;
    for (int x = 1; x <= n / 2; x++) {
        if (n % x == 0) {
            sum += x;
        }
    }
    return sum;
}