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

#python #алгоритм #python_3x #математика

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


  2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до
10 без остатка.
  
  Найдите такое наименьшее положительное число, которое делится на все числа от 1 до 20?


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

calculate = True
max_number = 20
min_number = 1
current_divisible = 2520
count = 0

while 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 = False

print(min_number) # 232792560


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

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

Ответы

Ответ 1

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

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

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

long gcd(long m, long n)
{
    while(m && n) if (m < n) n %= m; else m %= n;
    return (m == 0L) ? n : m;
}

long lcm(long m, long n)
{
    return (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;
}