RU
EN
question@mail.ru
·
Более рациональная реализация алгоритма перебора, чтобы найти наименьшее положительное число, которое делится на все числа от 1 до 20
📁 python
Есть задачка:
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
·
Вообще-то говоря, вам надо просто искать наименьшее общее кратное для всех чисел от 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;}Войдите чтобы оставить ответ