Project Euler #5

projecteuler-problem5.cs

// 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
// What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
// https://projecteuler.net/problem=5
void Main()
{
	var bop = new BagOfPrimes();
	
	Enumerable.Range(1, 20)
		.Select(d=>dividersOf(d).GroupBy(_=>_).Aggregate(bop, (c,n) => c.add(n)).value)
		.Dump();
}

class BagOfPrimes
{
	Dictionary<int, int> data = new Dictionary<int, int>();

	public int value
	{
		get
		{
			return data.Aggregate(1, (c, kv) => 
				c * Enumerable.Range(1, kv.Value).Aggregate(1, (cc, n) => cc * kv.Key));
		}
	}
	
	public BagOfPrimes add(IEnumerable<int> primes)
	{
		foreach (var g in primes.GroupBy(_=>_))
		{
			if (!data.Keys.Contains(g.Key))
			{
				data[g.Key] = 0;
			}

			data[g.Key] = Math.Max(g.Count(), data[g.Key]);
		}
		
		return this;
	}
}

IEnumerable<int> dividersOf(int n)
{
	var dividers = Enumerable.Range(2, Convert.ToInt16(Math.Sqrt(n)));

	var firstP = dividers.FirstOrDefault(p => n % p == 0);

	if (firstP == 0)
	{
		return new List<int>(new int[] { n });
	}

	return new List<int>(dividersOf(n / firstP)).Prepend(firstP);
}