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, anint
on some compilers may not produce the correct answer. Along
is guaranteed to hold at least 32 bits, or over 4 billion unique values, so I used along
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