5
\$\begingroup\$

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);
                    Console.ReadLine();
                }
            }             
        }
\$\endgroup\$
7
  • \$\begingroup\$ Why are you not checking 11 ? i think your list of divisor should include 11 \$\endgroup\$
    – aked
    Apr 17 '13 at 21:27
  • \$\begingroup\$ Thanks for the suggestion. Do you know order would that would give? \$\endgroup\$
    – phcoding
    Apr 17 '13 at 21:32
  • \$\begingroup\$ 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!). \$\endgroup\$
    – mellamokb
    Apr 17 '13 at 21:32
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – aked
    Apr 17 '13 at 21:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – mellamokb
    Apr 18 '13 at 4:14
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ this is cool !!! awesome \$\endgroup\$
    – aked
    Apr 18 '13 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.