Challenge: Amicable Numbers
Posted on: August 11, 2016 1:40:06 AMLet 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.
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));
}
}
}
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
persuasive essay writer [url="https://ukessayservice.net"]help starting an essay[/url] what can i write my essay on
VivienesrPa October 11, 2022 7:03:03 PM
custom essay writing sites [url="https://bestcampusessays.com"]buy essays[/url] buy cheap essay
DorolisasrPa November 19, 2022 7:15:48 AM
essay writing help for high school students [url="https://besteasyessays.org"]help with writing a essay[/url] cheap custom essay writing service
MartysrPa November 20, 2022 2:05:35 PM
cheap custom essay [url="https://bestessayreviews.net"]essay writers for pay[/url] i need help writing a narrative essay
MerolasrPa November 21, 2022 9:51:15 PM
admission college essay help [url="https://bestessaysden.com"]the help essays[/url] english essay help
AshlensrPa November 23, 2022 6:48:44 AM
buy essays [url="https://bestsessays.org"]essay writer services[/url] best essay services
CharitasrPa November 24, 2022 2:27:22 PM
mba admission essay writing service [url="https://buyacademicessay.com"]cheap essay buy[/url] best essay for you
NanicesrPa November 25, 2022 11:49:13 PM
what are good essay writing services [url="https://buy-eessay-online.com"]essay writing service law school[/url] admission essay editing service
ChelsaesrPa November 27, 2022 9:12:20 AM
how to be a good essay writer [url="https://buytopessays.com"]buy cheap essay online[/url] where can i buy an essay online
PennysrPa November 28, 2022 6:23:16 PM
Leave a Comment
