fork download
copy 
  1. # your code goes here
  2. import numpy as np
  3. #import time
  4. #import sys
  5. import functools 
  6. from math import sqrt
  7.  
  8. #print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}')
  9. #sys.setrecursionlimit(1001)
  10.  
  11. MAXSIZE = 1000000000
  12. m = np.zeros(MAXSIZE+1, dtype=np.int16)
  13.  
  14. #@functools.lru_cache(maxsize=None)
  15. def f(x, level=0, curmin = MAXSIZE) -> int:
  16.  
  17.     if level > curmin: return -1 # Отсечение - нет смысла лезть вглубь
  18.                                 # при наличии более короткого решения
  19.     if x == 1: return 0
  20.     if m[x]: return m[x]      # Сохраненное значение
  21.  
  22.     res = MAXSIZE;
  23.     for i in range(int(sqrt(x))+1, 0, -1):
  24.         if x%i: continue;
  25.         k = f(i+x//i-2, level+1, res);
  26.         if k < 0: continue;
  27.         if k < res:  res = k
  28.         m[x] = res+1
  29.     return m[x]
  30.  
  31. n = int(input("дай целое!"))
  32. #t0 = time.clock()
  33. rez = f(n)
  34. #t1 = time.clock()
  35. print( n, ": ", rez)
  36.  
  37. cur = m[n]
  38. while n>1:
  39.     for i in range(1,int(sqrt(n))+1):
  40.         if n%i: continue
  41.         if m[i+n//i-2] == cur-1:
  42.             n = i+n//i-2
  43.             cur -=1
  44.             print(i, end=' ')
  45.             break
  46. print("")
  47.  
  48. #print (t1-t0)
  49. #print(f.cache_info())
  50.  
Success #stdin #stdout 2.41s 27104KB
comments (?)
stdin
copy 
1000000000
stdout
copy 
дай целое!1000000000 :  8
250 504 87 13 5 2 2 1
https://ideone.com/zZXNtI
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!