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 <= n using sieve of erato."
np1 = n + 1
s = list(range(np1))
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1):
if s[i]:
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
def primeSum(n):
p=2
limit=math.floor(n/2)
for p in primes:
q=n-p
if(p>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).