Project Euler #5 - Lowest Multiple of 1 through 20

The root idea is to factorize all numbers in the range from 2 to 20 to the prime numbers with their multiplicity and find their production (with the multiplicity). The resulting number must be evenly divisible by all of the numbers from 1 to 20.

Get all primes from the range:

private static int[] GetPrimes(int n)
{
    BitArray a = new BitArray(n + 1, true);

    for (int i = 2; i <= Math.Sqrt(n); i++)
    {
        if (a[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                a[j] = false;
            }
        }
    }

    List<int> primes = new List<int>();
    for (int i = 2; i < a.Length; i++)
    {
        if (a[i])
            primes.Add(i);
    }

    return primes.ToArray();
}

This method gets all dividers (with multiplicity) of a given number:

private static IEnumerable<Tuple<int, int>> GetUniqueDividers(long n)
{
    List<int> tmp = new List<int>();
    List<int> pows = new List<int>();
    foreach (int p in Primes)
    {
        while (n != 1)
        {
            long rem = n % p;
            if (rem == 0)
            {
                n /= p;
                if (!tmp.Contains(p))
                {
                    tmp.Add(p);
                    pows.Add(1);
                }
                else
                    pows[tmp.IndexOf(p)]++;
            }
            else
                break;
        }
    }
    return tmp.Select((v, i) => new Tuple<int, int>(v, pows[i]));
}

The initialization:

private const int Max = 20;
private static readonly int[] Primes = GetPrimes(Max);

The method body:

int[] counts = new int[Max + 1];
for (int i = 2; i < counts.Length; i++)
{
    foreach (var div in GetUniqueDividers(i))
    {
        if (counts[div.Item1] < div.Item2)
        {
            counts[div.Item1] = div.Item2;
        }
    }
}

int outNumber = 1;
for (int i = 2; i < counts.Length; i++)
{
    if (counts[i] != 0)
    {
        outNumber *= (int)Math.Pow(i, counts[i]);
    }
}

Answer is in the outNumber variable.

Seems like I am a little bit late, but I would use a completely different approach(as if i would do with a pencil and paper) which returns the result immediately

Console.WriteLine(Calc(10));
Console.WriteLine(Calc(20));

List<int> Factors(int n)
{
    List<int> list = new List<int>();
    int i=2;
    while(i<=n)
    {
        if (n % i == 0)
        {
            list.Add(i);
            n /= i;
        }
        else
            i++;
    }
    return list;
}

int  Calc(int n)
{
    var factors = Enumerable.Range(2, n-1).Select(j => Factors(j)).ToList();

    int i = 2;
    int res = 1;
    while (i <= n)
    {
        if (factors.Count(l => l.Contains(i)) > 1)
        {
            factors.ForEach(l => l.Remove(i));
            res *= i;
        }
        else
            i++;
    }

    return res * factors.SelectMany(x => x).Aggregate((s, j) => s *= j);
}

A number of answers have pointed out some algorithmic changes, and some logic steps you can take, to calculate the result, but there's a simpler way to do it, which is not necessarily the fastest way, but it is still blazingly fast, and still very simple.

The algorithm you have by testing every number is obviously overkill, but, what about going through the basics of the process, and implementing it in code. What is the question actually asking? It's asking for the lowest common multiple of all the numbers 1 through 20.

Mathematically, 1 is a multiple of 1. so, we start there...

Then, find the multiple of 1 that is also a multiple of 2... to do that, we add the 1 to itself repeatedly, until we get a multiple of 2. This is easy, it is just once....

Now we have 2, which is a multiple of both 1, and 2. We want to find the multiple of both 1 and 2 (which is 2), that is also a multiple of 3, so, we check whether 2 is a multiple (it's not), so we add 2 to itself, which is 4. Is 4 a multiple? No, so we add 2 again, to get 6. Is 6 a multiple of 3? Yes. So, 6 is the lowest multiple of 1, 2, and 3. Now, we just repeat this process to 20.

Let's introduce some names here, lcm is the lowest common multiple, and sum is some value that is a multiple of lcm. If sum is a multiple of lcm, then it is also a multiple of everything that lcm is a multiple of.

The rest is actually easier to understand with code....., and it can be generalized very easily with a method like:

public static int GetLCM(int from, int to) {
    // lcm is the Lowest Common Multiple, which starts as just 'from'
    var lcm = from;
    for (int i = from; i <= to; i++) {
        var sum = lcm;
        while (sum % i != 0) {
            sum += lcm;
        }
        // sum is now the first multiple of lcm that is also a multiple of i
        lcm = sum;
    }
    return lcm;
}

Now, I have taken that concept and implemented it on Ideone, and you can see that it arrives at the right solution, using a simple algorithm, in almost no time.

Let's go through some basic rules:

• Everything is divisible by 1.
• If something is divisible by 16, then it's divisible by 2, 4, and 8.
• If something is divisible by 9, then it's divisible by 3.
• If something is divisible by both 16 and 9, then it's divisible by 6, 12, and 18.
• If something is divisible by both 16 and 5, then it's divisible by 10 and 20.
• If something is divisible by both 16 and 7, then it's divisible by 14.
• If something is divisible by both 9 and 5, then it's divisible by 15.

That leaves: 5, 7, 9, 11, 13, 16, 17, 19. Multiply those together and you get

232,792,560

Which of course is the answer.

Some of the other answers may have written the code to generate this list in general (i.e. for values other than 20). They don't seem to have commented the code in a way that's making it clear to me what they're doing.

Add a break statement when the test fails in your inner loop.

Just compute the lcm of all numbers from 1 to 20.

LCM of (a, b) is (a * b)/gcd(a, b) and the Euclids's algorithm for GCD is one of the earliest algorithm thaught in a class about functions and recursion.

I am not fluent in C# but here is an example in Scala :

object Euclid extends App {

       def gcd(a: Long, b: Long): Long = {  
           if (b == 0) a else gcd(b, a % b)
       }

       def lcm(a: Long, b: Long) = (a / gcd(a, b)) * b

       var answer = 1l
       for (i <- 2 to 20) answer = lcm(answer, i)

       println(answer)
}

Evaluating the complexities of algorithms is a must when trying to solve that kind of problems.

The complexity of Euclid's algorithm can be approximated by \$O(log(max(a,b)))\$. The LCM of numbers from 1 to n can be calculated in \$O(n.log(n))\$ steps and I think that this approach is the best proposed so far.

OK, here is a solution in Java, which should be more readable to a C# programmer:

public static int gcd(int a, int b) {
  if (b == 0) return a; else return gcd(b, a%b);
}

public static int lcm(int a, int b) {
  return b*(a/gcd(a, b));
}

public static int euler() {
  int answer = 1;
  for (int i = 2; i <= 20; i++) {
     answer = lcm(answer, i);
  }
  return answer;
}

[edit] Original code could overflow, be careful to use longs and doing the division before the multiplication in LCM.