Tags

, , , ,

From ProjectEuler.org:

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?

Image of C++ CodePretty straightforward: a nested loop that checks for divisibility inside another loop that counts up by 20 until the answer is found. Just a couple things I’ll say about this:

  • In constructing the inner loop, I counted down from 20 (instead of up from 1) because I figure fewer numbers are divisible by 20 and 19 than by 1 and 2. This way the first false condition is found sooner than later, and no time is wasted.
  • Further, every integer from 1 to 10 divides evenly into some integer from 11 to 20. Therefore it’s not necessary to check 1-10; 11-20 is enough.
  • I constructed my loop using a boolean flag, isDivisble, that is reset every time we increase the outer loop by 20. The flag allows me to break out of the inner loop as soon as I find a number that is not divisible, so no time is wasted.
  • Although my compiler allows me to use an int and still come up with the correct answer, the C++ standard only requires an int to hold 16 bits, or ~65,000 unique values (positive and negative). Since the answer is greater than 65,000/2, an int on some compilers may not produce the correct answer. A long is guaranteed to hold at least 32 bits, or over 4 billion unique values, so I used a long in my solution just as a best practice. With only that change, it takes twice as long to run. Efficiency is priority #1, people!
Project Euler #5 Solution

Project Euler #5 C++ Solution

C++ Code:

#include <iostream>

using namespace std;

bool isDivisible;

int main()
{
    for (long i = 2520; ; i += 20){
        isDivisible = true;
        for (int j = 20; j > 10; j--){
            if (!(i%j == 0)){isDivisible = false; break;}
        }
        if (isDivisible){cout << endl << "The smallest number evenly divisible by all integers between 1 and 20 is: " << i << "." << endl << endl; break;}
    }
    return 0;
}

Python won’t allow an indefinite range in a for loop, so I had to rewrite it to use a while loop. Same basic structure, though:

i = 2520

while True:
    isDivisible = True;
    for j in range(20, 10, -1):
        if i%j is not 0:
            isDivisible = False
            break
    if isDivisible:
        print ""
        print "The smallest number that is evenly divisible by all integers between 1 and 20 is " + str(i) + "."
        break
    else:
        i += 20
Advertisements