smallest number divisible by all numbers from 1 to 20? Project Euler question 5

I'm currently working my way through the questions on Project Euler and I am on question 5. Is this the best possible solution? Any suggestions welcomed!

List<int> divisors = new List<int>{ 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

int n = 1;

while (true)
{
n++;
foreach (int d in divisors)
{
if (n % d != 0) { break; }
if (d==20)
{
Console.Write(n);
}
}
}
• Why are you not checking 11 ? i think your list of divisor should include 11
– aked
Apr 17 '13 at 21:27
• Thanks for the suggestion. Do you know order would that would give? Apr 17 '13 at 21:32
• Not sure what you mean? Order of what? If you mean Big-O complexity, it would be O(n), whereas your current algorithm is probably O(n!). Apr 17 '13 at 21:32
• @phcoding what mellamokb mean is multiply all the prime factors of each number you will get your answer [2,3,4,5,6] 2*3*5*2=60
– aked
Apr 17 '13 at 21:40
• I was using n to refer to the number of input divisors (in this case 20). Worst case scenario is that all of your divisors share no common factors, and so you would have to loop 1 by 1 all the way to n! before you found the answer. It isn't a good idea to use the "output number" in the algorithm complexity because it obscures the real complexity. Apr 18 '13 at 4:14

The most optimal solution would be to calculate the LCM of 1 to 20 directly using the standard Euclidean algorithm.

// calculate GCD using Euclidean algorithm
public long GCD(long a, long b) {
if (b == 0)
return a;
else
return GCD(b, a % b);
}

// calculate LCM using simple formula based on GCD
public long LCM(long a, long b) {
var gcd = GCD(a, b);
return a * b / gcd;
}

// iteratively calculate LCM of 1 through 20
public static void Main(string args[]) {
long result = 1;

// loop through each value 1 to 20, and LCM with previous result
for (long n = 2; n <= 20; n++) {
result = LCM(result, n);
}

// print out the result
Console.WriteLine(result);
}

In terms of complexity, this algorithm is roughly O(n) for small n.

• this is cool !!! awesome
– aked
Apr 18 '13 at 0:48