Euler Problem 5 – Weekly Update

Forgot all about this until just before the deadline, so a little bit of a rushed job. Did try to get another colleague involved, but couldn’t get them to quite cross the line.

The ProblemEuler Problem 5

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?

My Solution

Initially I had a couple of thoughts. The raw solution would be to have a for loop, simply test the remainder of the division from 1 to 20.. until the right number was found. This could be coded long handed with numerous indented if… statements for each of the numbers 1..20. Then a while loop would have presented a better way of avoiding the nested loops. If the counter got to 0 for the while loop, then I’d found my number.

My next consideration was to think about what numbers wouldn’t need to be tested if bigger numbers succeeded, e.g anything divisible by 20 would also be divisible by 2 etc… This led me to a path to stop my calculations when hitting 8 as the counter.

Finally, the for loop didn’t need to go through all the numbers. It could start at 20, and then increment by 20 every time.

To test any efficiency gains, rather than using the default output from NetBeans I also logged the in milliseconds before starting and upon completion. Interestingly (and I can’t explain why), I took slightly longer to stop dividing at 8 rather than just continue through checking the lower numbers. When I say slower, only by 1 millisecond or so.

And so my final solution is as below, and takes approximately 70 milliseconds to complete.

boolean found = false;
int sum = 0;

for (int i = 20; !found; i = i + 20) {
   int starting = 19;
   boolean breakOut = false;

   while (!found && !breakOut) {
      if ((i % starting) == 0) {
         starting--;

         if (starting == 0) {
            sum = i;
            found = true;
         }
      } else {
         breakOut = true;
      }
   }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s