### Challenge: Amicable Numbers

Posted on: August 11, 2016 1:40:06 AM
This challenge describes an amicable number as:
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.
The challenge is to get the sum of all the amicable numbers less than 10,000.
Program.cs
```using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_21
{
internal class Program
{
private static int[] GetFactors(int num)
{
List factors = new List { 1, num };
int root = (int)Math.Sqrt(num);

for (int i = 2; i <= root; i++)
{
if (num % i == 0)
{
}
}

return factors.Distinct().OrderBy(i => i).ToArray();
}

{
int[] factors = GetFactors(num);
int sum = 0;

// don't include the actual num in the sum
for (int i = 0; i < factors.Length - 1; i++)
{
sum += factors[i];
}

return sum;
}

private static void Main(string[] args)
{
Dictionary cache = new Dictionary();
List amicableNumbers = new List();
int amicableCount = 0;

Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 9999; i > 0; i--)
{
int factorSum = 0;

if (!cache.ContainsKey(i))
{
cache[i] = factorSum;
}
else
{
factorSum = cache[i];
}

if (!cache.ContainsKey(factorSum))
{
}

if (cache[factorSum] == i && i != factorSum)
{
amicableCount++;
}
}
sw.Stop();

amicableNumbers = amicableNumbers.Distinct().OrderBy(i => i).ToList();

Console.WriteLine("Number of amicable numbers under 10000: {0}\r\nSum of amicable numbers: {2}\r\nAmicable Numbers: {3}\r\nElapsed time: {1} ms", amicableCount, sw.ElapsedMilliseconds, amicableNumbers.Sum(), string.Join(", ", amicableNumbers));
}
}
}
```
From another challenge, we know how to easily and quickly calculate the factors of a number. So we can easily add to that logic by summing the factors to help us get an amicable number. I decided to cache the values, even though there really aren't many numbers we'd have to calculate twice. It ended up skimming off a couple of milliseconds.

No comments yet, be the first to leave one.

Recent Blog Activity
Blog Archive