-
Notifications
You must be signed in to change notification settings - Fork 0
/
FermatFactorization.py
73 lines (60 loc) · 1.91 KB
/
FermatFactorization.py
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# Fermat Prime Factorization method with Python
import math
from decimal import Decimal
def fermat_factorization(n):
"""
This function takes single integer as parameter and returns 2 factors of n based on Fermat Factorization Technique.
:param n: int
:return: int,int
"""
if n % 2 == 0:
return n // 2, 2
sqrt_num = math.sqrt(n) # calculating square root
i = math.ceil(sqrt_num) # rounding off to nearest integer greater than sqrt_num
j = math.sqrt(i ** 2 - n)
a, b = 0, 0
if j.is_integer(): # check if x is integer before 1st iteration
j = int(j)
a = i + j
b = i - j
else:
while isinstance(j, float):
i += 1
j = math.sqrt(i ** 2 - n)
# print(i, j)
if Decimal(j) % 1 == 0:
# print(i, j)
a = (int(i + j))
b = (int(i - j))
# print('Factors: ', int(i + j), 'x', int(i - j))
break
return a, b
def prime_check(n):
"""
Checks if input parameter is a prime number or not by using Fermat Factorization method
:param n: integer
:return: bool
"""
i, j = fermat_factorization(n)
if (i == n and i != 1) or (i == 1 and j == 2):
return True
else:
return False
def primes_in_range(n1, n2):
"""
This function takes 2 integer inputs and returns a list of prime numbers between them (both numbers inclusive)
:param n1: integer
:param n2: integer
:return: list
"""
prime_list = []
for i in range(n1, n2 + 1):
if prime_check(i):
prime_list.append(i)
return prime_list
if __name__ == '__main__':
number = int(input('Enter Integer to Factorize: '))
x, y = fermat_factorization(number)
print(x, "\t", y)
p1 = primes_in_range(1, 50000)
print(len(p1))