# 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 search<lsta[mid]:
return(Bsearch(lsta,low,mid-1,search))
elif search>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>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])<=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)

• For generating primes, see Sieve of Eratosthenes - Python – Janne Karila Mar 31 '14 at 17:04
• Why wait until you've compiled the entire list to start outputting? – kojiro Mar 31 '14 at 19:20
• @DavidHarkness: The condition is P is a prime, its reverse is a prime, and its reverse is not equal to P. 2 meets the first two conditions but not the third. – Eric Lippert Mar 31 '14 at 22:10
• @StijndeWitt: No, there is no (widely-understood) definition of prime number that requires that mandates primes to be odd. That seems to be a misunderstanding. – Oddthinking Apr 1 '14 at 15:42
• @Oddthinking: Interesting because I remember thinking it was really silly that 2 was not a prime... Seems my first instinct was right after all... However I also had this same feeling about one but there I am definitelt wrong. BTW, your username is very suitable now :) – Stijn de Witt Apr 1 '14 at 19:32

With an efficient implementation of the sieve of Eratosthenes and the general approach outlined by @tobias_k, I have it running in 0.5 seconds, including the printing. Try with this:

def primes(limit):
# Keep only odd numbers in sieve, mapping from index to number is
# num = 2 * idx + 3
# The square of the number corresponding to idx then corresponds to:
# idx2 = 2*idx*idx + 6*idx + 3
sieve = [True] * (limit // 2)
prime_numbers = set([2])
for j in range(len(sieve)):
if sieve[j]:
new_prime = 2*j + 3
for k in range((2*j+6)*j+3, len(sieve), new_prime):
sieve[k] = False
return prime_numbers

• You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. – Toby Speight Apr 19 '18 at 10:42

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:


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.

• Thank you for your suggestions, Yeah I am now convinced it cannot be reduced less than what you added here, maybe I should write this program in C or C++ I guess.. – Akash Rana Mar 31 '14 at 17:17
• Your basic approach seems to me th eright one, but that's not the best of implementations of the Sieve of Erathostenes. And checking for p > 9 is redundant with p != q and is slowing things down for most numbers. – Jaime Mar 31 '14 at 17:27
• @Jaime Thanks for the pointers! I improved my sieve a bit using the three-parameters-(x)range instead of multiplying, but left the only-odd-numbers trick out -- for readability, and to not entirely copy your answer (+1). Cut down the time by another 20% (with yours even 40%). – tobias_k Mar 31 '14 at 18:27
• When i is a prime, the first non-prime to remove from the sieve is i*i, not i*2. I suppose you where trying to write i**2? That should cut your time bit quite a bit more, as it avoids a lot of redundant sieving. – Jaime Mar 31 '14 at 18:46
• if p != q and q in ps and q not in final: can save an in test if you rewrite as if p < q and q in ps: – Peter Taylor Apr 19 '18 at 10:28

# Use a fast prime generator

See below the best pure python prime generator from this thread (python 3):

def primes(n):
sieve = [True] * (n//2)
for i in range(3, int(n**0.5) + 1, 2):
if sieve[i//2]:
sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
return [2] + [2*i+1 for i in range(1, n//2) if sieve[i]]


# Constant time lookups using a python set

You could use the native python module bisect to perform the binary search. But it is simpler and faster to use a set of primes. See this page about time complexity:

prime_set = set(primes(upper_bound))


# Keep the main loop simple

Loop over the primes, reverse the prime, check that its value is over the original prime (to avoid duplicates) and then look for it in the primes set:

def palindromic_primes(upper_bound):
prime_set = set(primes(upper_bound))
for p in prime_set:
r = int(str(p)[::-1])
if r > p and r in prime_set:
yield p


# Separate the running logic from the solving logic

It makes it easier to parametrize and test your program (python 3):

if __name__ == '__main__':
t = time.time()
upper_bound = int(eval(sys.argv[1]))
generator = palindromic_primes(upper_bound)
for score, x in enumerate(generator, 1):
print(x)
delta = time.time() - t
status = "Score = {} in {:.3f} s".format(score, delta)
print(status, file=sys.stderr)


# Results for several upper bounds

$python3 palindromic_primes 1e6 > /dev/null Score = 5592 in 0.077 s$ python3 palindromic_primes 1e7 > /dev/null
Score = 40829 in 0.836 s
\$ python3 palindromic_primes 2e7 > /dev/null
Score = 59525 in 1.722 s

• I wonder whether reversing numbers using the int → str → int conversion is a limitation. Would the obvious arithmetic approach be faster? – Toby Speight Apr 20 '18 at 13:03
• @TobySpeight I just benchmarked it, the string approach is about 3 times faster. – Vincent Apr 20 '18 at 14:31
• That was a surprise to me - thanks for demonstrating that! – Toby Speight Apr 20 '18 at 14:34

Using numba you can even run this code in less than one second.

('Time Taken : ', 0.7115190029144287)


The code, slightly based on the version of @jaime, should be rewritten with numpy.arrays. See here

import numpy as np
import numba
from time import time
start = time()

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 search<lsta[mid]:
return(Bsearch(lsta,low,mid-1,search))
elif search>lsta[mid]:
return(Bsearch(lsta,mid+1,high,search))
elif search==lsta[mid]:
return True
else:
return False

def primes(limit):
# Keep only odd numbers in sieve, mapping from index to number is
# num = 2 * idx + 3
# The square of the number corresponding to idx then corresponds to:
# idx2 = 2*idx*idx + 6*idx + 3
sieve = [True] * (limit // 2)
prime_numbers = set([2])
for j in range(len(sieve)):
if sieve[j]:
new_prime = 2*j + 3
for k in range((2*j+6)*j+3, len(sieve), new_prime):
sieve[k] = False
return list(prime_numbers)

@numba.jit('void(uint8[:])', nopython=True)
def primes_util(sieve):
ssz = sieve.shape[0]
for j in xrange(ssz):
if sieve[j]:
new_prime = 2*j + 3
for k in xrange((2*j+6)*j+3, ssz, new_prime):
sieve[k] = False

def primes_numba(limit):
sieve = np.ones(limit // 2, dtype=np.uint8)
primes_util(sieve)

return [2] + (np.nonzero(sieve)[0]*2 + 3).tolist()

final = [] # used to hold the final output values

lsta = primes_numba(LIMIT)

for i in xrange(len(lsta)):
# prime number compared with reversed counterpart
if(int(str(lsta[i])[::-1])<=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 xrange(len(final)-1,0,-1):
print(final[i])
print(13)

end=time()
print("Time Taken : ",end-start)

• You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. – Toby Speight Apr 19 '18 at 10:43

This got around 11000 points using a limit of 13.5 million, in roughly 2 seconds

Basically my strategy is to create a lookup list out made of bools, where at the end of each cycle in my main loop, the next true value with a higher index than the current indexed value is guaranteed to be prime.

The first thing i do when I evaluate a new prime, is to eliminate its multiples from the rest of the list.

After that I get the reverse of my current prime value and perform:

• Case1 If the reversed value is lower than the non reversed, I check to see if it is also a prime using my lookup list. If its also a prime value I only add the original value.
• Case2 if reversed value is higher than my overall limit I perform a simple check on it using a common prime evaluating function. If it is prime I add the non reversed prime
• Case3 If the reversed value higher than the non reversed prime and lower than the limit I will ignore it seeing as it will be found again under Case1

from time import time
def is_prime(n):
for i in xrange(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def DoMath(limit):
start = time()
lkup = [True,True,True] +[ bool(ii%2) for ii in xrange(3,limit)]
with open("text.txt", 'w') as file:
index = 3
r_index = 0
str_index = ''
while index <  limit:
if lkup[index]:
for ii in xrange(index*2, limit, index):
lkup[ii] = False
str_index = str(index)
r_index = int(str_index[::-1])
if r_index >= limit and is_prime(r_index):
file.write(str_index+'\n')
elif r_index < index and lkup[r_index]:
file.write(str_index+'\n')
index += 1
end=time()
print("Time Taken : ",end-start)

• You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. – Toby Speight Apr 19 '18 at 10:43