аватар question@mail.ru · 01.01.1970 03:00

Более рациональная реализация алгоритма перебора, чтобы найти наименьшее положительное число, которое делится на все числа от 1 до 20

Есть задачка:

2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка.

Найдите такое наименьшее положительное число, которое делится на все числа от 1 до 20?

Задачку эту я решил, написав плохо оптимизированный алгоритм полного перебора вариантов.

calculate = Truemax_number = 20min_number = 1current_divisible = 2520count = 0while calculate:   for i in range(2, max_number + 1):       if current_divisible % i == 0:          count += 1          min_number = current_divisible       else:          count = 0          break   current_divisible += 1   if count == max_number:      calculate = Falseprint(min_number) # 232792560

Ответом этой задачки является число 232792560, но мой алгоритм считает это очень долго. Около 15 минут.

Никак не могу понять, как лучше оптимизировать данный код.

аватар answer@mail.ru · 01.01.1970 03:00

Вообще-то говоря, вам надо просто искать наименьшее общее кратное для всех чисел от 1 до 20 :) Элементарно, никакого перебора, мгновенно.

Я могу набросать код на C или C++, Python не знаю.

Вот код - алгоритм Евклида для НОД, затем НОК...

long gcd(long m, long n){    while(m && n) if (m < n) n %= m; else m %= n;    retu (m == 0L) ? n : m;}long lcm(long m, long n){    retu (m/gcd(m,n))*n;}int main(int argc, const char * argv[]){    long Res = 1;    for(int i = 2; i <= 20; ++i)    {        Res = lcm(Res,i);    }    cout << Res << endl;}

Последние

Похожие