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)
                {
                    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.

Comments


free chat on gay webcam [url="https://chatcongays.com"]gay chat roulettye[/url] free gay radom ewb chat

GenniesrPa September 16, 2022 12:03:51 AM

admission essay editing services [url="https://au-bestessays.org"]essays on the help[/url] help write essay

MarrissrPa September 20, 2022 1:08:31 AM

paid essay writers [url="https://bestcampusessays.com"]best essay writing services[/url] custom essays essay help

DorolisasrPa September 20, 2022 8:20:14 PM

essaywriting service [url="https://besteasyessays.org"]help essay 123[/url] admissions essay help

MartysrPa September 21, 2022 6:40:21 PM

cheap essay papers [url="https://bestessayreviews.net"]essay writing service canada[/url] custom essay station

MerolasrPa September 22, 2022 2:41:30 PM

custom law essay [url="https://bestessaysden.com"]write my essay discount code[/url] buy an essay online cheap

AshlensrPa September 23, 2022 10:26:38 AM

english essay writing service [url="https://bestsessays.org"]cheapest custom essays[/url] write my essay service

CharitasrPa September 25, 2022 12:00:58 AM

best essay cheap [url="https://buyacademicessay.com"]top essay writing websites[/url] cheap essay papers

NanicesrPa September 25, 2022 6:59:11 PM

essays service [url="https://buy-eessay-online.com"]the best essay writing services[/url] cheap essay writing services

ChelsaesrPa September 26, 2022 2:38:59 PM

custom essay paper writing [url="https://buytopessays.com"]college essay help long island[/url] cheapest custom essay writing

PennysrPa September 27, 2022 9:50:25 AM

best website for essays [url="https://cheapessaywritingservice1.com"]us essay writers[/url] best essay writer

TammiesrPa September 28, 2022 5:35:59 AM

mba essay editing services [url="https://customessays-writing.org"]best college essay writing service[/url] professional custom essays

RhiamonsrPa September 29, 2022 9:11:30 PM

buy essays [url="https://customessaywwriting.com"]top essay writing services[/url] professional college application essay writers

CharosrPa September 30, 2022 4:03:33 PM

personal essay help [url="https://customs-essays-writing.org"]essays help[/url] Who wants to write my essay

DronasrPa October 1, 2022 10:42:58 AM

cheap essay services [url="https://geniusessaywriters.net"]essay on helping others[/url] essay writing services reviews

LeilahsrPa October 3, 2022 2:57:45 AM

custom essays cheap [url="https://howtobuyanessay.com"]essay writing service recommendation[/url] buy an essay cheap

CthrinesrPa October 4, 2022 12:50:25 AM

Leave a Comment