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