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

Possible duplicate of [Elegant Python code for Integer Partitioning](https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning) — Aaron_ab, Feb 04 '19 at 13:37
There are websites where you can hire a programmer to work for you. This is not one of them. — David, Feb 04 '19 at 13:38
Please try hard to solve a problem before you ask a question. And please make your answer is specific. Do you need help with the coding? if so, what part? do you need help with the algorithm? if so, in what way? are you looking for better time complexity that brute force? Try to separate your your problem to its core aspect that you're really stuck with. — Elliott, Feb 04 '19 at 13:41
https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — eagle33322, Feb 04 '19 at 17:23

iacob · Accepted Answer · 2019-02-14T22:52:08.327

2

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

edited Feb 14 '19 at 22:52

answered Feb 04 '19 at 13:49

iacob

20,084
6
92
119

Ohh, i was again checking if y is prime or not by again doing same checks as i have done before in the first loop, never came to me that i could just check the number against the list of primes, thanks , it helped a lot. – Souvikavi Feb 04 '19 at 13:58
The above code got a bug......for example check the case when m = 4. The primes are [2 3]. The above code shows True for m = 4 – Siva Srinivas Kolukula Feb 13 '19 at 09:32
@sivasrinivaskolukula I suggest you read the question again. "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." `p=2, q=2` is a valid solution for `4` so it should return `True`. – iacob Feb 13 '19 at 09:39
Your final *modular* code example doesn't work for me. `partition(4)` returns `False` and `partition(11)` returns `True` -- both of which are wrong. In fact, `primes(4)` returns `[3, 4]`. What am I not understanding? – cdlane Feb 14 '19 at 21:59
@cdlane ah true, there's a mistake, will fix it now. – iacob Feb 14 '19 at 22:22
I can't get your suggested modification to the OP's code to work for me. (E.g. 8 and 6 return the wrong result.) It seems that the `return False` shouldn't be in an `else` clause but rather a standalone clause *after* the `for` loop. Or some such. – cdlane Feb 14 '19 at 22:32

score 1 · Answer 2 · answered Feb 04 '19 at 17:22

1

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

answered Feb 04 '19 at 17:22

Souvikavi

108
1
10

The above code got a bug......for example check the case when m = 4. The primes are [2 3]. The above code shows True for m = 4. – Siva Srinivas Kolukula Feb 13 '19 at 09:32
@SivaSrinivasKolukula, as explained in response to your similar comment on @ukemi's solution, the result for `4` should be `True` as it partitions `[2, 2]`. – cdlane Feb 14 '19 at 22:03

Sreeraj · Answer 3 · 2019-02-14T18:38:03.517

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)

score 1 · Answer 4 · answered Jan 26 '21 at 09:48

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

score 1 · Answer 5 · answered Feb 25 '21 at 16:21

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.")

This is the best code I have with me to share with :) – Vamsi Feb 25 '21 at 16:22 — Vamsi, Feb 25 '21 at 16:22

score 0 · Answer 6 · answered Feb 13 '19 at 09:53

0

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

answered Feb 13 '19 at 09:53

Siva Srinivas Kolukula

1,251
1
7
14

This code returns `False` for `primepartition0(4)` and `primepartition0(6)`, both of which have valid solutions. – cdlane Feb 14 '19 at 22:01

cdlane · Answer 7 · 2019-02-14T22:50:32.657

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

Alain T. · Answer 8 · 2021-01-29T19:11:38.257

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)

score 0 · Answer 9 · answered Jan 28 '21 at 11:46

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

Sarvekash Aggarwal · Answer 10 · 2021-01-29T11:35:02.367

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])

Check if a number can be divided into prime partitions

10 Answers10