Goldbach’s Conjecture in Python

Input Format

Input starts with an integer n (1 ≤ n ≤ 100) indicating the number of cases. The following n lines each contain a test case of a single even number x (4 ≤ x ≤ 32000).

Output Format

For each test case x, give the number of unique ways that x can be represented as a sum of two primes. Then list the sums (one sum per line) in increasing order of the first addend. The first addend must always be less than or equal to the second to avoid duplicates.

Sample Input

2
26
100

Sample Output

26 has 3 representation(s)
3+23
7+19
13+13

The above problem was originally posted in 2013 ICPC North America Qualifier, I encountered it in HackerRank's Round-I Holiday Cup contest.

My Python 3.x Code

import math
import time
def sieve(n):
    "Return all primes q):
            break
        if(q in primes):
            out.extend([p,q])
    print (n,"has",round(len(out)/2),"representation(s)")
    for i,j in zip(out[0::2],out[1::2]):
        print (i,"+",j,sep='')

    print ("")

primes = sorted(set(sieve(32000)))
for __ in range(int(input())):
    out = []
    primeSum(int(input()))

This code almost took over 5 seconds for larger values of n but ran less than second in most cases. Is it because of time taken to output all those representations for larger values (because 32000 has over 300 representations.

Can this be optimized? and also review my general coding (I'm new to python).

Pass more arguments to functions

primes is global, but passing it as an argument to primeSum is trivial:

def primeSum(n, primes):

and then:

primeSum(int(input()), primes)

This makes the reasoning about and testing the function easier.

Do not modify random global variables

out.extend([p,q]) where out is a global variable. Don't. It makes the code impossible to use in different situations and therefore wastes your programming effort.

Do not print from a computation function

primeSum should find a prime sum. Printing the couples nicely is the job for another function. Again a computer friendly return format improves re-usability.

Remove dead code

You write:

limit=math.floor(n/2)

But limit is never been used, so delete that line.

Also p=2 can be eliminated as it does nothing.

Meaningful names

Avoid single-letter names, be descriptive. Good names can really make the difference between un-readable and readable code. And remember to use snake_case in Python.

Final version

Putting all my advice together gives this nice prime_sum function:

def prime_sums(number, primes):
    """
    Checks how a number may be written as a sum of two primes.

    >>> list(prime_sums(100, sorted(set(sieve(100)))))
    [(3, 97), (11, 89), (17, 83), (29, 71), (41, 59), (47, 53)]
    """
    for prime in primes:
        difference = number - prime
        if(prime > difference):
            break
        if(difference in primes):
            yield (prime, difference)

StackExchange Code Review Q#112642, answer score: 4