blob: c369645511b07cba23c81404eb3e6ff3bfefc82a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)
|
