CODEWITHSUNDEEP
pythonalgorithmgoldbach-conjecture
Sidharth Gopalakrishnan
Sidharth Gopalakrishnan

Reputation: 63

Duplicate Pairs while implementing Goldbach Conjecture Implementation in Python

As the title suggests I am working on finding all the pairs of prime numbers that satisfy the goldbachs conjecture for any given number n. This is my implementation of the algorithm:

import math
def prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True
def Plist(n):
    res=[]
    for i in range(2,n+1):
        if prime(i):
            res.append(i)
    return res
def Goldbach(n):
    res=[]
    plist=Plist(n)
    hmap={}
    for num in plist:
        diff=n-num
        if diff in plist and (num not in hmap.keys()):
             res.append((num,diff))
             hmap[num]=1
             
       
    return res

This algorithm is giving me redundant pairs and I want to know how to get rid of one redundant pair, Example (3,23) and (23,3)

Upvotes: 0

Views: 64

Answers (2)

Andy Richter
Andy Richter

Reputation: 189

You are going too far in your checks. You need to only check plist until the prime is = to n//2. After that you get duplicates. This will work:

from math import isqrt
def prime(n):
   if n <= 3: return n>1
   if n%6 not in [1,5]: return False
   for i in range(5,isqrt(n)+1,6):
      if n%i==0 or n%(i+2)==0:return False
   return True
    
def Plist(n): 
   res = [2,3] 
   for i in range(5,n+1,6): 
       if prime(i): 
         res.append(i)
       if prime(i+2) and (i+2)<=n: 
         res.append(i+2)
   return res

def Goldbach(n):
        res=[]
        plist=Plist(n)
        for num in plist:
            if num > n//2: break
            diff=n-num
            if diff in plist:
                 res.append((num,diff))
        return res
             
if __name__=="__main__":
   for x in range(20,30,2):
      gb = Goldbach(x) 
      for a,b in gb: 
         print(f"{x} = {a} + {b}")

Output:

20 = 3 + 17
20 = 7 + 13
22 = 3 + 19
22 = 5 + 17
22 = 11 + 11
24 = 5 + 19
24 = 7 + 17
24 = 11 + 13
26 = 3 + 23
26 = 7 + 19
26 = 13 + 13
28 = 5 + 23
28 = 11 + 17

You can skip the plist entirely like:

def Goldbach(n):
    res=[]
    #plist=Plist(n)
    if n == 4: return [(2,2)]
    for num in range(3,n//2+1,2):
        diff=n-num
        if prime(diff) and prime(num):
             res.append((num,diff))
    return res

Upvotes: 0

islam abdelmoumen
islam abdelmoumen

Reputation: 664

import math
def prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True
def Plist(n):
    res=[]

    for i in range(2,n+1):
        if prime(i):
            res.append(i)
    return res
def Goldbach(n):
    plist=Plist(n)
    res=[]
    while plist:
        i = plist.pop()
        for j in plist:
            p = (i,j)
            if sum(p)==n:
                res.append(p)
    return res
         

print(Goldbach(26))

Upvotes: 0

Related Questions