Project Euler - Problem 5

Welcome to week 4 of my Project Euler series.

Problem 4:
What is the smallest number divisible by each of the numbers 1 to 20?

Details:
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?

Code:

// What is the smallest number divisible by each of the numbers 1 to 20?

class Problem5

{

    static void Main(string[] args)

   {

      bool notFound = true;

      int number = 20;

      while (notFound)

      {

         bool evenlyDivisible = true;

         for (int i = 1; i <= 20; i++)

         {

            if (number % i != 0)

               evenlyDivisible = false;

         }

         if (!evenlyDivisible)

            number++;

         else

            notFound = false;

      }

      Console.WriteLine(number);

      Console.Read();

   }

}

Solution:

This one was really easy. A simple brute force approach yields the result in no time.  Sadly the days of brute forcing our way through this problems is coming very quickly to an end.

Since the end result was unclear, I chose to go with a while loop. A do-while loop would have worked just as well since I new it was going to run at least once, but that is simply a matter of personal opinion.  I prefer the while loop (when I have a choice) simply because it allows you to see the condition, when reading the code, before you actually get to what it will be doing.  A basic bool is used as the test criteria so I can change it with an if check in the loop.  I start the loop off at number 20, because no number under that is going to be divisible by 20.  At least not in the sense of what they are looking for.  In all honesty it could have started a great deal higher than that, but I chose to let the program do all the work, with only hard coding what can be gained from the question.  For each consecutive number I check if it is divisible by every number between 1 and 20.  If it is then we have a winner!  Toss it on the console and wait for the user to press any key to continue.  If it is not a match then I move right along to the next number. It doesn't get much simpler than that.

After this one, we have a couple of more brute force approaches, then things really start to take off.  As I said in the beginning, these problems are not overly difficult. Some of them are of course, but there are some that are really simple.  The thing that complicates them is that they are stretched out.  For example finding the first number that is divisible by every number between 1 and 5 could be done by hand. It would take some time, effort, sweet, and tears, but it is in the end possible.  So is this problem, but from the time that is needed it is no longer what a normal person would consider solvable by hand.  A couple of magic keystrokes later and a couple of seconds wait and we have an answer. That is really the beauty of programming.

Until next time...

Enjoy!