From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab11/lab11.py | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
 create mode 100644 lab11/lab11.py

(limited to 'lab11/lab11.py')

diff --git a/lab11/lab11.py b/lab11/lab11.py
new file mode 100644
index 0000000..c369645
--- /dev/null
+++ b/lab11/lab11.py
@@ -0,0 +1,26 @@
+import math
+
+
+def fermat_factorization(n):
+    start_x = math.ceil(math.sqrt(n))
+    cur_x = start_x
+    squared_y = 0
+    for x in range(start_x, (n + 1) // 2):
+        cur_x = x
+        squared_y = math.sqrt(x ** 2 - n)
+        if math.isclose(int(squared_y), squared_y, rel_tol=1e-20):
+            break
+
+    multiplier_p = cur_x + squared_y
+    multiplier_q = cur_x - squared_y
+    if multiplier_p == n // multiplier_q:
+        factors = [int(multiplier_p), int(multiplier_q)]
+        print(f"Простые множители для {n}: {factors}")
+    else:
+        print(f"Метод Ферма не нашел подходящую пару множителей для {n}")
+
+
+if __name__ == "__main__":
+    print("Введите нечётное целое число n:")
+    n = int(input())
+    fermat_factorization(n)
-- 
cgit v1.2.3