diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
| commit | 0be2be0a92f992bf8ee9eff701cb19658a1e7544 (patch) | |
| tree | 5d855004fd8cc067a594475c0a666eb01f0ceefa /lab11 | |
| parent | 056f59346b727c9367998a423551eaba52854fce (diff) | |
Diffstat (limited to 'lab11')
| -rw-r--r-- | lab11/lab11.py | 26 |
1 files changed, 26 insertions, 0 deletions
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)
|