Project Euler - Problem 5: 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?

---

Explanation:

We are going to factor all numbers from 1 to 20 and keep track of the maximum number of prime factors - then multiply them to find the smallest product. You may have know this from school as the Least Common Multiple of a set of numbers.

If we look at the example of 2520 for numbers 1 to 10 more thoroughly we may be able to explain a little clearer what the intention is. Let's start with finding the primes which are 2, 3, 5, and 7. We know that all numbers up to this are going to be made up of these primes. However, the number 8 is 2*2*2 so we need to multiply our product by 4 (2*2). The number 9 is similar but for 3 (3*3) so we will need to multiple our product by 3. Our final product comes out to $2^3*3^{}*5*7=\mathrm{2520}\text{.}$

Solution:

My solution goes through all numbers between 2 and the max number (in this case 20), it first checks if the number is prime - if it is it adds it to the collection of primes. If it is not prime it then goes over the list of prime numbers and tries to find the factors for it. Using the factors, I then update the collection of factors I have seen. When I have gone through all the numbers I go through the collection and generate the product. It looks something like this:

    private static List<int> primesFound = new List<int>();
    
    private static void Problem5(int maxNumber)
    {
        int[] smallestMultiple = new int[maxNumber];
        
        for(int i = 2; i <= maxNumber; i++)
        {
            if(IsPrime(i))
            {
                primesFound.Add(i);
                smallestMultiple[i-1] = 1;
                continue;
            }
            
            foreach(int prime in primesFound)
            {
                int factorCount = GetFactorCountOfPrime(i, prime);
                if(smallestMultiple[prime-1] < factorCount)
                {
                    smallestMultiple[prime-1] = factorCount;
                }
            }
        }
        
        int product = 1;
        for(int i = 0; i < maxNumber; i++)
        {
            for(int multiple = smallestMultiple[i]; multiple > 0; multiple--)
            {
                product *= i+1;
            }
        }
        
        Console.WriteLine(product);
    }
    
    private static bool IsPrime(int number)
    {
        foreach(int prime in primesFound)
        {
            if(number % prime == 0)
            {
                return false;
            }
        }
        
        return true;
    }
    
    private static int GetFactorCountOfPrime(int number, int prime)
    {
        int factorCount = 0;
        while(number % prime == 0)
        {
            number /= prime;
            factorCount++;
        }
        return factorCount;
    }

An online sample of which can be found here.

Summary

The execution time of this is not too bad, I averaged 400,000 seconds on tutorialspoint.com. We could optimize it slightly by skipping the factoring of numbers that are less than the prime factoring them - but since the sample space is so small I do not think it will be noticeable. We could try to combine the logic for determining a prime and the factoring to reduce the amount of looping done, but that will impact the readability a little. Short of cutting the sample space by a square root I do not really see much that can be done to improve the solution. Let me know what you think in the comments.

---

Edit:

I couldn't get this out of my head last night, and just before bed, I thought about the possibility of using logarithms to calculate. I am not sure if this will make it any faster, but it may.