**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?`

Pretty 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!

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