@SureshPatil/

# Prime Numbers

## No description

Files
• main.py
main.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
```
```import random
import math
import time

def trial(n, d, r):
a = random.randint(2, n-1)
check = pow(a, d, n) - 1
if check%n == 0:
return True
for s in range(0, r):
check = pow(a, d * pow(2, s), n) + 1
if check%n == 0:
return True
return False

def isPrime(p):
if p%2 == 0:
return False
r = 0
d = p - 1
while True:
if d % 2 != 0:
break
else:
r += 1
d = d//2
for i in range(10):
if trial(p, d, r) == False:
return False
return True

def isSquare(n):
val = int(math.sqrt(n))
if val * val == n:
return True
else:
return False

def factor(n):
val = int(math.sqrt(n))
if isSquare(n):
return [val, val]
for x in range(val + 1, n):
ySquare = x**2 - n
if isSquare(ySquare):
return [int(x - math.sqrt(ySquare)), int(x + math.sqrt(ySquare))]

def findPrime(number):
if number % 2 == 0:
number += 1
while isPrime(number) == False:
number += 2
return number

def run_trial(n):
# n = 512
print('Between 2 to the', n - 1, 'th and 2 to the', n, 'th power')
start = time.perf_counter()
primes = []
for x in range(2):
rando = random.randint(2**(n-1) + 1, 2**n)
primes.append(findPrime(rando))
end = time.perf_counter()
findPrimeTime = end - start
print('Found Primes', primes[0], 'and', primes[1])
product = primes[0]*primes[1]
print('Product', product)
start = time.perf_counter()
factors = factor(product)
end = time.perf_counter()
factorTime = end - start
print('Factored to (', factors[0], ',', factors[1], ')')
print('Finding primes took', findPrimeTime)
print('Finding product took', factorTime)

def run_multiple_trials(n, numTrials):
primeFindingTimes = []
factoringTimes = []
print('Between 2 to the', n - 1, 'th and 2 to the', n, 'th power')
for x in range(0, numTrials):
start = time.perf_counter()
primes = []
for x in range(2):
rando = random.randint(2**(n-1) + 1, 2**n)
primes.append(findPrime(rando))
end = time.perf_counter()
findPrimeTime = end - start
primeFindingTimes.append(findPrimeTime)
product = primes[0]*primes[1]
start = time.perf_counter()
factors = factor(product)
end = time.perf_counter()
factorTime = end - start
factoringTimes.append(factorTime)

print('Average time to find two primes', sum(primeFindingTimes)/len(primeFindingTimes))
print('Average time to factor product', sum(factoringTimes)/len(factoringTimes))

# run_trial(26)
# run_multiple_trials(28, 10)
# end = time.perf_counter()
# print(end - start)
print(factor(2494279923802253606287472092668310204875649561581672691813431640440219048972006082731965879))```