Check if a number can be divided into prime partitions

Question

Can somebody solve this problem on Python ?

A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0 and both p and q are prime numbers.

Write a Python function that takes an integer m as input and returns True if m can be partitioned as primes and False otherwise.

Tried this, but does not work for all testcases, for example it should return True for 3432, it returns False.

def partition(num):
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)


    for x in primelist:
        y= num-x
        for z in range(2,y):
            if y%z == 0:
                return False

        return True

Answer 1

The error lies in the second for loop. You are looping through possible primes x, and wish to then check that y = num - x is also prime.

The error in your logic is that in the second for loop, if the first element in the loop y = num - x is not prime, it will return False, without checking any of the other possible values.

You could correct this by moving the return False statement out one loop, but since you have already generated a list of primes less than num, primelist (and since y = num - x, (if prime y exists) it will be in this list), you can just check for membership of the list:

    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
        # If no such y is prime, not possible
        else:
            return False

Note: I would advise making the logic of your script more modular, separating out the prime list generator into its own function:

def partition(num):
    """
    Return True if there exist primes x,y such that num = x + y.
    Else return False.
    """
    primelist = primes(num)
    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
    # If no such y is prime, not possible
    else:
        return False

def primes(num):
    """Return list of all primes less than num."""
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)
    return primelist

Answer 2

final solution i got:

def primepartition(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            y= m-x
            if y in primelist:
                return True
        return False

Answer 3

Slight Variation of your code:

def primepartition0(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            for y in primelist:
                if x != y and x+y == m:
                    return True
        return False   

Answer 4

The given below code can hopefully give you the correct output.

def factors(n):
    factorslist = []
    for i in range(1, n+1, 1):
        if n % i == 0:
            factorslist.append(i)
    return(factorslist)    

def prime(n):
    if factors(n) == [1, n] and n > 1:
        return(True)

def primelist(n):
    primenolist = []
    for i in range(1, n+1, 1):
        if prime(i) == True:
            primenolist.append(i)
    return(primenolist)

def primepartition(m):
    if m > 0:
        primenolist = primelist(m)
        checklist = []
        for p in primenolist:
            q = m - p
            if q in primenolist and p > 0 and q > 0:
                checklist.append((p,q))
        if len(checklist) > 0:
            return(True)
        else:
            return(False)
    else:
        return(False)

Answer 5

An alternate approach that attemps to reduce the amount of code necessary:

def primepartition(m):
    if m > 3:
        for number in range(m // 2, m - 1):
            difference = m - number

            for psuedoprime in range(2, int(number ** 0.5) + 1):
                if number % psuedoprime == 0 or difference > psuedoprime and difference % psuedoprime == 0:
                    break
            else:  # no break
                return number, difference  # as good a non-False result as any other...

    return False

Answer 6

Another approach, Initially, we store all prime elements upto m and check for pair of primes whose sum equal to m

def primepartition(a):
l=[2]#since 'a' should be >=2 for below loops, we took here 2(1st prime).
for i in range(2,a):
        flag=0
        for j in range(2,i):
            if i%j==0:
                flag=0
                break
            else:
                flag=1
        if flag==1:
            l.append(i)
for i in l:
    for j in l:
        if i+j==a:
            return True
return False

Answer 7

If you're not required to produce the actual primes but only test if there exists a pair of primes p and q such that p+q == N, you could make this very simple based on the Goldbach conjecture. All even numbers can be expressed as the sum of two primes. So return True if the number is even and check if N-2 is prime for odd numbers (because 2 is the only even prime and that's the only prime that will produce another odd number when starting from an odd number). This will boil down to a single prime test of N-2 only for odd numbers.

def primePart(N):
    return N%2==0 or all((N-2)%p for p in range(3,int(N**0.5)+1,2))

primePart(3432)  # True

primePart(37+2)  # True

primePart(13+41) # True

primePart(123)   # False
    

If you want to actually find a pair of primes that add up to N, you can generate primes up to N and return the first prime >= N/2 where N - prime is one of the primes already found:

def findPQ(N):
    if not primePart(N): return
    if N%2: return 2,N-2
    isPrime = [0]+[1]*N
    for p in range(3,N,2):
        if not isPrime[p]: continue
        if 2*p>=N and isPrime[N-p]: return p,N-p
        isPrime[p*p::p] = [0]*len(isPrime[p*p::p])

output:

findPQ(3432)      # (1723, 1709)

findPQ(12345678)  # (6172879, 6172799)

To go beyond 10^9 you will need a more memory efficient algorithm than the sieve of Eratosthenes that is just as fast. This can be achieved with a dictionary of multiples of primes to skip:

def findPQ(N):
    if not primePart(N): return
    if N%2: return 2,N-2
    skip,primes = {},{2}
    for p in range(3,N,2):
        if p in skip:
            prime = skip.pop(p)
            mult  = p + 2*prime
            while mult in skip: mult += 2*prime
            if mult <= N: skip[mult] = prime
        else:
            if 2*p>=N and N-p in primes: return p,N-p
            if p*p<=N: skip[p*p]=p
            if 2*p<=N: primes.add(p)

output (takes a while but doesn't bust memory space):

findPQ(1234567890)  # (617283983, 617283907)    

Answer 8

def factors(n):
    factlist = []
    for i in range(1,n+1):
        # Since factors of 2 cannot be primes, we ignore them.
        if n%i==0 and i%2!=0:
            factlist.append(i)
    return factlist

def isprime(n):
    return(factors(n)==[1,n])

def preimesupto(n):
    primelist = []
    if n>=2:
        primelist.append(2)
    for i in range(n):
        if isprime(i):
            primelist.append(i)
    return primelist

def primepartition(n):
    if n<0:
        return False
    primelist = preimesupto(n)
    for i in primelist:
        j = n-i
        if j in primelist:
            return True
    else:
        return False

Answer 9

def checkprime(number):
fact=1
for r in range(2,number):
if number%r==0:
  fact=fact+1
return(fact<2)

def primepartition(m):

for i in range(2,m):

flag=0
if checkprime(i) and checkprime(m-i)==True:
  flag=1
  break
return(flag==1)

def matched(s):
list_of_string=list(s)
for y in range(len(list_of_string)):
if list_of_string[y]=='(':
for z in range(y,len(list_of_string)):
    if list_of_string[z]==')':
      list_of_string[y]='@'
      list_of_string[z]='@'
      break
 return('('not in list_of_string and ')'not in list_of_string)

 def rotatelist(l,k):
 if k>len(l):
 k=int(k%len(l))
 return(l[k:]+l[0:k])

Answer 10

n=int(input("Enter any number: "))
list=[]
for num in range(0,n + 1):  
 if num > 1:  
     for i in range(2,num):  
       if (num % i) == 0:  
           break  
       else:
           list.append(num)
if (n<= 1):
    print("False")
    #print("It is not positive ")
else:
    for i in list:
        y = num -i
        if (y in list):
            print("True")
            #print(y,"+",i,"=",n)
            #print(i,"+",y,"=",n)
            #print("The number can be expressed as the sum of two prime numbers.")
            break
    else:
        print("False")
        #print("The number can not be expressed as the sum of two prime numbers.")