-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathgoldbach.py
85 lines (55 loc) · 1.74 KB
/
goldbach.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
"""
To know more about the Goldbach's conjecture try out their
wikipedia page linked here https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
"""
import math
# This code makes sure sieve is called exactly once.
def run_once(f):
def wrapper(*args, **kwargs):
if not wrapper.has_run:
wrapper.has_run = True
return f(*args, **kwargs)
wrapper.has_run = False
return wrapper
primes = []
@run_once
def sieveSundaram() -> None:
"""
In general Sieve of Sundaram, produces
primes smaller than (2*x + 2) for a
number given number x. Since we want
primes smaller than MAX (10000), we reduce
MAX to half. This array is used to
separate numbers of the form i + j + 2*i*j
from others where 1 <= i <= j
This function is contributed by chandan_jnu, GFG.
Modified By Abraar13.
"""
marked = [False] * (int(10000 / 2) + 100)
for i in range(1, int((math.sqrt(10000) - 1) / 2) + 1):
for j in range((i * (i + 1)) << 1, int(10000 / 2) + 1, 2 * i + 1):
marked[j] = True
primes.append(2)
for i in range(1, int(10000 / 2) + 1):
if (marked[i] == False):
primes.append(2 * i + 1)
def findPrimes(num : int) -> list[str]:
sieveSundaram()
i , ans = 0, []
while (primes[i] <= num // 2):
diff = num - primes[i]
if diff in primes:
ans.append(f"{primes[i]} + {diff} = {num}")
i += 1
ans.insert(0, f"There are {len(ans)} combinations : ")
return ans
def print_goldbach(num : int) -> None:
if (num <= 2 or num % 2 != 0):
raise TypeError("Goldbach's conjecture it true for even num > 2")
lst = findPrimes(num)
for item in lst:
print(item)
if __name__ == "__main__":
print_goldbach(4)
print_goldbach(20)
print_goldbach(100)