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!

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

### Like this:

Like Loading...

*Related*