namemkazaza

Факторизация

Sep 23rd, 2020
1,033
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def long_sqrt(a):
  2.     x = a
  3.     while True:
  4.         x1 = (x * x + a) // (2 * x)
  5.         if x1 >= x:
  6.             return x
  7.         x = x1
  8.  
  9.  
  10. def factor(n):
  11.     x = long_sqrt(n)
  12.     while True:
  13.         x += 1
  14.         z = x * x - n
  15.         c = long_sqrt(z)
  16.         if c ** 2 - z == 0:
  17.             return x - c, x + c
  18.  
  19.  
  20. f1 = open('input.txt', 'r')
  21. f2 = open('output.txt', 'w')
  22. n = int(f1.read())
  23. a, b = factor(n)
  24. f2.write(str(a) + '\n' + str(b))
  25. f1.close()
  26. f2.close()
  27.  
RAW Paste Data