Project Euler: Problem #5 in Ruby

Question

I'm trying to solve Problem #5 in Project Euler. The code works for the example, when I check the numbers from 1 to 10 I get 2520 as a result, which is right. But when I check for the numbers from 1 to 20, the code doesn't stop running.

Here it is:

num = 0

while true

    num += 1
    check = true

    for i in 1..20

        break unless check

        check = num%i==0

    end

    break if check

end

File.open("__RESULT__.txt", "w+").write num

Answer 1

The solution for that problem can not be found by just calculating every possible solution. The solution is so big, that it will take days (maybe years) to calculate.

There is a smarter solution using prime numbers to write down the numbers.

The example that is given (2520 is the smallest number that is divisable by the numbers 1 through 10) can be written down like this:

1 = 1 (can be skipped)  = 2^0 * 3^0 * 5^0 * 7^0
2 = 2 (prime)           = 2^1 * 3^0 * 5^0 * 7^0
3 = 3 (prime)           = 2^0 * 3^1 * 5^0 * 7^0
4 = 2^2                 = 2^2 * 3^0 * 5^0 * 7^0
5 = 5 (prime)           = 2^0 * 3^0 * 5^1 * 7^0
6 = 2 * 3               = 2^1 * 3^1 * 5^0 * 7^0
7 = 7 (prime)           = 2^0 * 3^0 * 5^0 * 7^1
8 = 2^3                 = 2^3 * 3^0 * 5^0 * 7^0
9 = 3^2                 = 2^0 * 3^2 * 5^0 * 7^0
10= 2 * 5               = 2^1 * 3^0 * 5^1 * 7^0

Now the smallest number that can be divided by these, can be calculated by using the maximum power that is used on each prime:

2^3 * 3^2 * 5^1 * 7^1 = 2520

The same can be performed (even by hand) on the numbers 1 through 20

Last hint: the answer is larger than 100.000.000 but less that a billion, so it can be calculated in minutes if done efficiently

Answer 2

The Question essentially asks you to find the LCM of the first 20 numbers...

lcm = 1
for i = 2 to 20
   lcm = (i * lcm) / gcd(lcm,i)

Answer 3

A far simpler solution would be to use your algorithm but increment by 2520 rather than 1, here is my C++ solution.

#include <iostream>
using namespace std;

int main()
{
    int check = 2520;
    int i = 11;
    while (i != 20)
    {
        i ++;
        if (check % i != 0)
        {
            check +=2520;
            i = 1;
        }
    }
    cout << check << endl;
    return 0;
}

As you can see above, I also start at the number 2520, and set i to equal 11. We can make these optimizations, as we have been given the necessary information in the question.