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&gt;high:
        return False
    else:
        mid=int((low+high)/2)
        if search&lt;lsta[mid]:
            return(Bsearch(lsta,low,mid-1,search))
        elif search&gt;lsta[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&gt;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 counterpart
    if(int(str(lsta[i])[::-1])&lt;=lsta[len(lsta)-1]):
        if Bsearch(lsta,i+1,len(lsta)-1,int(str(lsta[i])[::-1])):
            if not(int(str(lsta[i])[::-1])==lsta[i]):
                final.append(str(lsta[i]))

for i in range(len(final)-1,0,-1):
    print(final[i])
print(13)
end=time()
print("Time Taken : ",end-start)
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.