import time
import sys
import functools
from math import sqrt

#print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}')
i=0
sys.setrecursionlimit(10000)

@functools.lru_cache()
def f(x):
    global i
    i +=1
    if i%250==0: print(i)
    if x <=1: return 0
    return 1 + min([ f(m + x // m - 2)  for m in range(1,int(sqrt(x))+1) if x%m==0])

x = int(input("дай целое!"))
t0 = time.clock()
print( f(x))
t1 = time.clock()
print (t1-t0, '  i=', i)

дай целое!1024
250
500
750
...
3250
3500
7

0.12052656332407201   i= 3636

дай целое!1040
250
500
750
1000

=============================== RESTART: Shell ===============================

import signal

def run_pdb(signal, frame):
    import pdb
    pdb.Pdb().set_trace(frame)


def do_something():  # Основная логика
    ...

if __name__ == '__main__':
    signal.signal(signal.SIGBREAK, run_pdb)
    do_something()