Почему мой код не перестает работать? - PullRequest
Новая
       7

Почему мой код не перестает работать?

2 голосов
/ 04 июня 2010

Я пытаюсь решить Проблема № 5 в Project Euler. Код работает для примера, когда я проверяю числа от 1 до 10, в результате я получаю 2520, и это правильно. Но когда я проверяю числа от 1 до 20, код не останавливается.

Вот оно: 

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

Ответы [ 3 ]

11 голосов
/ 04 июня 2010

Решение этой проблемы не может быть найдено, просто вычисляя каждое возможное решение. Решение настолько велико, что на его вычисление уйдут дни (а может и годы).

Существует более разумное решение, использующее простые числа для записи чисел.

Приведенный пример (2520 - наименьшее число, которое делится на числа от 1 до 10) можно записать так: 

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

Теперь наименьшее число, которое можно разделить на них, можно рассчитать, используя максимальную мощность, которая используется для каждого простого числа: 

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

То же самое можно выполнить (даже вручную) с номерами от 1 до 20

Последний совет: ответ больше 100.000.000, но меньше миллиарда, поэтому можно вычислить в минутах, если сделать эффективно

0 голосов
/ 29 сентября 2010

Гораздо более простым решением было бы использование вашего алгоритма, но с шагом 2520, а не 1, вот мое решение C ++. 

#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;
}

Как вы можете видеть выше, я также начинаю с номера 2520 и устанавливаю i равным 11. Мы можем провести эту оптимизацию, поскольку нам была предоставлена ​​необходимая информация в вопросе.

0 голосов
/ 09 июня 2010

Вопрос, по сути, просит вас найти LCM первых 20 чисел ... 

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