Project Euler Solution 21

Problem Statement

Evaluate the sum of all amicable pairs under 10000.

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 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Solution

The question itself clearly gives us what an amicable pair means and to know more about it click here.

The important thing here is finding divisors in a small running time. Here goes an example of what I have used in my program:

Let us consider the number 220 and find the divisors. Our first step is to find the square root of 220 which is 14.832. But we are going to take only the floor value which is 14. The divisors of 220 less than 14 are 1, 2, 4, 5, 10 and 11. So now to find the other divisors, divide 220 by 2, 4, 5, 10 and 11 to get 110, 55, 44, 22 and 20.

Implementation

#include <stdio.h>#include <math.h>
int SumOfDivisors(int number);int main(){    int M, N = 1, SumOf_amic_num = 0, index = 0;    int amic_num[100] = { 0 };    for (M = 2; M <= 10000; M++)    {        N = SumOfDivisors(M);        if (M == SumOfDivisors(N) && M != N)            SumOf_amic_num = SumOf_amic_num + M;    }    printf("%d", SumOf_amic_num);    return 0;}int SumOfDivisors(int number){    int sum_div = 1, div1;    for (int div = 2; div <= sqrt(number); div++)    {        if (number % div == 0)        {            sum_div = sum_div + div;            div1 = number / div;            if (div1 != div)                sum_div = sum_div + div1;        }    }    return sum_div;}

Sample Output