Monday, March 16, 2015

Project Euler - Smallest Multiple

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? (LCM of 1 to 20)
https://projecteuler.net/problem=5

public class Euler5
    {
        List> allFactors = new List>();
        List finalFactors = new List();

        public long Solve(int start, int end)
        {
            for (int i = start; i <= end; i++)
            {
                var factor = FindFactors(i);
                allFactors.Add(factor);
            }

            foreach (var factorsList in allFactors) 
            {
                foreach (var factor in factorsList)
                { 
                    if (!finalFactors.Contains(factor)) finalFactors.Add(factor);
                    int countCurrent = factorsList.Where(x => x == factor).Count();
                    while (countCurrent > finalFactors.Where(x => x == factor).Count())
                    {
                        finalFactors.Add(factor);
                        countCurrent--;
                    }
                }
            }

            return finalFactors.Aggregate(1, (a, b) => a * b);
        }

        private List FindFactors(int num)
        {
            List result = new List();

            while (num % 2 == 0)
            {
                result.Add(2);
                num /= 2;
            }

            int factor = 3;
            while (factor * factor <= num)
            {
                if (num % factor == 0)
                {
                    result.Add(factor);
                    num /= factor;
                }
                else factor += 2;
            }

            if (num > 1) result.Add(num);
            return result;
        }
    }