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) { Listfactors = new List { 1, num }; int root = (int)Math.Sqrt(num); for (int i = 2; i <= root; i++) { if (num % i == 0) { factors.Add(i); factors.Add(num / i); } } return factors.Distinct().OrderBy(i => i).ToArray(); } private static int GetFactorsSum(int num) { 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)) { factorSum = GetFactorsSum(i); cache[i] = factorSum; } else { factorSum = cache[i]; } if (!cache.ContainsKey(factorSum)) { cache[factorSum] = GetFactorsSum(factorSum); } if (cache[factorSum] == i && i != factorSum) { amicableCount++; amicableNumbers.Add(i); amicableNumbers.Add(factorSum); } } 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.

Recent Blog Activity

Blog Archive

© 2016 - 2024 - Justin Sommercorn