C++ Solution for ProjectEuler Problem #5

Question

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Is there a more elegant solution in C++?

#include <iostream>
using namespace std;
int main(){
 long long num = 1;
 int divMin = 1;
 int divMax = 20;
 int tempDivMax = divMax;
 while(true){
 if(num % tempDivMax == 0)
 {
 tempDivMax--;
 if(tempDivMax == divMin){
 cout << num << endl;
 break;
 }
 }else{
 tempDivMax = divMax;
 num++;
 }
 }
 return 0;
}

• JAD: Did you look at the solution provided by project Euler themselves? Algorihmically, that's a good place to start. Once you entered the solution on their website, it can be found here: projecteuler.net/overview=005
• Martin R: There are far more efficient ways to get the result. I would suggest to have a look at earlier questions about this problem, such as codereview.stackexchange.com/q/80500/35991 or codereview.stackexchange.com/q/202307/35991, where better approaches are explained.
• slepic: The smallest positive number evenly divisible by numbers 1 to 20 is a constant and the fastest solution would be to print the constant. cheers.
• Loki Astari: Find all the primes between one and twenty.
• slepic: The answer is LCM([1,2,...., 20]) = 2*3*2*5*7*2*3*11*13*2*17*19 = 232792560

Answer 1

Code review

To start with, some points about your code:

• using namespace std; is something I consider a code smell. It doesn't save much time and I find it clearer to see exactly where cout etc. are coming from. Additionally, it clutters your namespace although I myself haven't run into name collisions with the STL being an issue before.

• It looks like your condition to exit the while loop is tempDivMax == divMin. Use this rather than while (true) to make it clearer what behaviour is intended.

• You are also performing two iterations inside a single loop: num is being incremented from 1 until it succeeds and tempDivMax is being decremented until it equals divMin. Split these into separate loops! The code will be clearer to read and will be just as fast. The outer loop I would turn completely into a for loop for (; tempDivMax != divMin; ++num) { ... } and but the inner one I would make a while loop while (tempDivMax > divMin && num % tempDivMax == 0) { ... } since the long condition expression makes for some rough reading when condensed into a for loop.

• Finally, define your constants before your working variables and declare them as const. I would even do this outside of the main function.

This leaves you with:

#include <iostream>
const int DIV_MIN = 1;
const int DIV_MAX = 20;
int main() {
 long long num = 1;
 int tempDivMax = DIV_MAX;
 for (; tempDivMax > DIV_MIN; ++num) {
 tempDivMax = DIV_MAX;
 while (tempDivMax > DIV_MIN && num % tempDivMax == 0) {
 --tempDivMax;
 }
 }
 std::cout << num << std::endl;
 return 0;
}

A "more elegant" solution...

== Obligatory code below is untested ==

I'd imagine they're looking for something like this?

For something to be divisible by a number, it must have at least that number's prime factors. Furthermore, in any given number below 20, there can be a maximum of $$\lfloor{log_p(20)}\rfloor$$ copies of the prime factor $$p$$

The following snippet calculates the product of these.

#include <iostream>
const int DIV_MAX = 20;
const int[] PRIMES = {2, 3, 5, 7, 11, 13, 17};
int main() {
 int result = 1;
 for (int p : PRIMES) {
 int tmp = 1;
 while (tmp < DIV_MAX) tmp *= p;
 result *= tmp;
 }
 std::cout << result << std::endl;
 return 0;
}

• slepic: Your untested solution is wrong. Firstly, 19 is also a prime. Secondly it produces 1418659424 which is obviously not divisible at least by 10. If I added 19 to the set of primes it produced 1034943840 which is not the smallest solution.
• slepic: Aha sry, the numbers are fake because it overflown 32 bit int. It produces much greater numbers with long. 6254891042400 without 19, and 2258015666306400 with 19, they both are evenly divisible by 1 to 20 but they are far more than the smallest solution. Smallest solution is 232792560.
• slepic: Actually 6254891042400 even cannot be divisble by 19 because that prime was not used for multiplication.

Answer 2

Avoid using namespace std

The std namespace isn't designed for wholesale importation into the global namespace like that, and it contains lots of names that are likely to disagree with your own identifiers (possibly leading to unexpected overloads, and thus a different to expected behaviour). Leave the standard library identifiers where they belong, and enjoy clearer and more reliable code.

Avoid the infinite loop

Sometimes there's really a need for an infinite loop, but this doesn't appear to be one of those. What we have here looks like two loops, with the if switching between states. It's more honest and easier to read if we show the two loops clearly:

for (num = 1; num < LLONG_MAX; ++num) {
 bool dividesAll = true;
 for (int i = divMin; i < divMax; ++i) {
 if (num % i) {
 dividesAll = false;
 break;
 }
 if (dividesAll) {
 std::cout << num << '\n';
 return 0;
 }
}

It becomes clearer again if we refactor a function:

bool dividesAll(long long n, int min, int max) {
 for (int i = min; i < max; ++i) {
 if (n % i) {
 return false;
 }
 return true;
}

and use it:

for (num = 1; !dividesAll(num, divMin, divMax); ++num) {
 // empty body
}
std::cout << num << '\n';
return 0;

Use unsigned types

There's no use of negative numbers, so we can stick to unsigned integer types here.

Improve the algorithm

Brute-force search is a poor choice of technique for this problem. Like all Project Euler challenges, you should be able to use some mathematical reasoning to produce much more efficient code.

• slepic: Mathematic reasoning in this case can easily produce the answer itself. Getting the answer with a program is an overkill. If it was asking for 1 to N then it would be a differrent thing. The problem can be rephrased as finding LCM of the numbers 1 to 20. I can do this with a calculator just hitting multiplication button several times. Or even on paper quite easily...