This will be much faster. It does fewer prime checks, usually less than 100, and does not check numbers that are even for prime.
**With GMPY2:**
$ python3 goldbach.py 12345678912345678
This is a test of Goldbach's Conjecture that for all even integers
greater than 2 there are two primes that add up to that even number.
61 + 12,345,678,912,345,617 = 12,345,678,912,345,678
42 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 goldbach.py:16(goldbach)
1 0.000 0.000 0.000 0.000 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
37 0.000 0.000 0.000 0.000 {built-in method gmpy2.gmpy2.is_prime}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
$ python3 goldbach.py 4444444444444444444444
This is a test of Goldbach's Conjecture that for all even integers
greater than 2 there are two primes that add up to that even number.
257 + 4,444,444,444,444,444,444,187 = 4,444,444,444,444,444,444,444
144 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 goldbach.py:16(goldbach)
1 0.000 0.000 0.000 0.000 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
139 0.000 0.000 0.000 0.000 {built-in method gmpy2.gmpy2.is_prime}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
**With my Home Grown IsPrime:**
$ python3 goldbach.py 12345678912345678
This is a test of Goldbach's Conjecture that for all even integers
greater than 2 there are two primes that add up to that even number.
61 + 12,345,678,912,345,617 = 12,345,678,912,345,678
42 function calls in 3.869 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 3.869 3.869 <string>:1(<module>)
1 0.000 0.000 3.869 3.869 goldbach.py:16(goldbach)
37 3.869 0.105 3.869 0.105 goldbach.py:6(IsPrime)
1 0.000 0.000 3.869 3.869 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
$ python3 goldbach.py 1000000000
This is a test of Goldbach's Conjecture that for all even integers
greater than 2 there are two primes that add up to that even number.
71 + 999,999,929 = 1,000,000,000
47 function calls in 0.001 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.001 0.001 <string>:1(<module>)
1 0.000 0.000 0.001 0.001 goldbach.py:16(goldbach)
42 0.001 0.000 0.001 0.000 goldbach.py:6(IsPrime)
1 0.000 0.000 0.001 0.001 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
**Listing:**
# Goldbach's Conjecture tester.
from gmpy2 import is_prime
import sys
import cProfile
# or use home grown IsPrime
def IsPrime(n):
if (n == 2 or n == 3):
return True
if (n <= 1 or n % 2 == 0 or n % 3 == 0):
return False
for i in range(5, int(n**.5)+1, 6):
if (n % i == 0 or n % (i + 2) == 0):
return False
return True
def goldbach(number):
if number == 4:
print("\n2 + 2 = 4\n")
return
elif IsPrime(number - 3):
print(f"\n3 + {number-3:,} = {number}\n")
return
else:
for p in range(5, number, 6): # just odds after 3
if IsPrime(p) and IsPrime(number-p):
print(f"\n{p:,} + {number-p:,} = {N:,}\n")
return
elif IsPrime(p+2) and IsPrime(number-(p+2)):
print(f"\n{p+2:,} + {number-(p+2):,} = {N:,}\n")
return
raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}")
if __name__=="__main__":
N = 1
args = len(sys.argv)
if args > 1:
N = int(sys.argv[1])
print("This is a test of Goldbach's Conjecture that for all even integers")
print("greater than 2 there are two primes that add up to that even number.\n")
while (N < 3 or N%2):
N = int(input("Please enter an even number > 3 to check with Goldbach's Conjecture> "))
cProfile.run('goldbach(N)')