Project Euler - 05

[Petcheco]

Hello, guys.

Here's the challenge:

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?

I wrote my code:

#include <iostream>
#include <cmath>

using namespace std;

#define MAX_VALUE 2793510720

unsigned int  Smallest_Evenly_Divisable = 0;

void Show_Number(unsigned int);


void Show_Number(unsigned int Smallest_Evenly_Divisable)
{
    cout << "\n\n" << Smallest_Evenly_Divisable << endl;
}

int main()
{
   unsigned i = 0;

    for (i = 2520; i < MAX_VALUE; i++)
    {
        if ( i % 2 == 0 && i % 3 == 0 && i % 4 == 0 && i % 5 == 0 && i % 7 == 0 && i % 8 == 0 && i % 9 == 0 && i % 11 == 0
             && i % 13 == 0 && i % 17 == 0 && i % 19 == 0)
        {
            Smallest_Evenly_Divisable = i;
            Show_Number(Smallest_Evenly_Divisable);
            i = MAX_VALUE;
        }
    }
    return 0;
}

and got 116396280 as the answer. However, the official answer is 232792560.

But here's the thing: 116396280 < 232792560 and 116396280 is evenly divisable by {1,2,3...20}.

Am I missing something? It seems to me that my answer is correct. I even created a program to do the 116396280%i, i in {1,2,3...20} operation to be sure; it checks out.

Any help would be appreciated.

Petcheco.

[tinstaafl]

There must be a bug in your testing algorithm 116396280 / 16 equals 7274767.5

Rather than a naive approach, you'll find, using a Lowest Common Multiplier(lcm) algorithm that uses a Greatest Common Divisor(gcd) algorithm much more efficient:

int gcd(int a, int b)
{
    int t;
    while (b > 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}
int lcm(int a, int b)
{
    return (abs(a * b)) / gcd(a, b);
}
int main()
{

    long num = 1;
    for (int i = 1; i < 20; i++)
    {
        num = lcm(num, i);
    }

    cout <<  num << '\n';

    cin.get();
    return 0;
}

[Petcheco]

Thank you, sir. I'll look into that.

But could you point out what is wrong with my code?

Petcheco

[Petcheco]

By adding the following piece of code: && i%16 == 0 && the program works. However, like you said, it's a very brute-force, inneficient approach.

[rubberman]

Working out efficient algorithms is a key part of computer science. Good math skills helps. Also, don't be afraid of trying other approaches to solving the problem at hand. As someone once said, there is more than one way to skin a cat. Try different approaches and test them for efficiency, keeping in mind the KISS principle.

[Petcheco]

Well said, mate.

I'm programming as a hobby and it's been quite fun. The Project Euler is a remarkable tool; I'll be sure to make the most of it and improve my skills.

[rubberman]

Yes, I can see that it can be a good teaching tool. Enjoy! I hope we have helped you in your self-education endeavors. I always say, never let school get in the way of your education! :-)

[Petcheco]

You are definitely helping me a lot. I don't get much time to practice (going to college eats a large chunk of time) and all this help here is much appreciated.