Count distinct primes, discarding palindromes, in under 2 seconds

Problem Statement


Generate as many distinct primes P such that reverse (P) is also prime
and is not equal to P.


Output:

Print per line one integer( ≤ 1015 ). Don't print more than
106 integers in all.


Scoring:

Let N = correct outputs. M= incorrect outputs. Your score
will be max(0,N-M).


Note: Only one of P and reverse(P) will be counted as correct. If both
are in the file, one will be counted as incorrect.


Sample Output

107 13 31 17 2


Explanation

Score will be 1. Since 13,107,17 are correct. 31 is
incorrect because 13 is already there. 2 is incorrect.


Time Limit

2 sec(s) (Time limit is for each input file.)


Memory Limit

256 MB


Source Limit

25 KB

My Problem

I have tried quite hard to optimize the solution, but the min possible time this program took was : 16.452 secs

My question is, is it possible to optimize the following code further, is it possible to reduce execution time to 2 secs, if we are given that we have to use the Python language.

```
from time import time
start = time()
lsta=[] # empty list used to hold prime numbers created by primes function
LIMIT = pow(10,6)

# binary search function
def Bsearch(lsta,low,high,search):
if low>high:
return False
else:
mid=int((low+high)/2)
if searchlsta[mid]:
return(Bsearch(lsta,mid+1,high,search))
elif search==lsta[mid]:
return True
else:
return False

# prime number creating function using sieve of Eras** algorithm
def primes(LIMIT):
dicta = {}
for i in range(2,LIMIT):
dicta[i]=1
for i in range(2,LIMIT):
for j in range(i,LIMIT):
if i*j>LIMIT:
break
dicta[i*j]=0
for i in range(2,LIMIT):
if(dicta[i]==1):
lsta.append(i)

final = [] # used to hold the final output values
primes(LIMIT)
for i in range(len(lsta)):
# prime number compared with reversed counte

There are a few things you could optimize:

• If you (or the grading server?) are running this on Python 2.x, you should definitely use xrange instead of range (about 2 seconds on my system)

• In your prime sieve, you have to check the multiples only if the current number is a prime (down to 1s); also, instead of multiplying, count by multiples of is

• use a regular array instead of a dictionary in the sieve (0.8s)

• don't do that string-conversion and reversing more often than necessary; also instead of implementing your own binary search, just use sets for quick lookup (0.4s)

My version (updated):

def primes(limit):
    numbers = [0, 0] + [1] * (limit-2)
    for i in xrange(2, limit):
        if numbers[i]:
            for k in xrange(i**2, limit, i):
                numbers[k] = 0
    return set(i for i, e in enumerate(numbers) if e)

ps = primes(LIMIT)
final = set()
for p in ps:
    q = int(str(p)[::-1])
    if p != q and q in ps and q not in final:
        final.add(p)

Not sure whether this get's the running time down from 16s to 2s in your case, but it might be a start. As a desperate measure, you could decrease LIMIT -- better to find not quite as many than to timeout.

StackExchange Code Review Q#45857, answer score: 13