0
0 комментариев

Пояснение:
Есть натуральное число x, его можно представить как произведение двух натуральных чисел m и n (x=m*n). Далее x нужно заменить на m+n-2 (x=m+n-2). И это все необходимо выполнять, пока x не станет равно 1

x может быть в пределах миллиарда

Пример:
В программу поступило число 6.

6=3*2   3+2-2=3
6=6*1   6+1-2=5
 
3=3*1   3+1-2=2
5=5*1   5+1-2=4
 
2=2*1   2+1-2=1 - x=1, останавливаемся (до единицы мы дошли за 3 замены)
4=2*2   2+2-2=2

Мои попытки

from math import sqrt
 
def isint(n):
    return not(n%1)
 
def f(n):
   count = 0
   while(True):
      x=sqrt(n)
      if(n<=1):
         return count
      if(isint(x)):
         n=x+x-2
      else:
         x=int(x)
         while(isint(n/x)==False):
            x=x-1
         if(x<=0):
             return count
         n=int((n/x)+x-2)
      count+=1
print('Минимальное кол-во попыток для числа 6 = ',f(6))

P.S. Мой алгоритм делает ошибки, но некоторые числа он все же считает


Добавить комментарий