# 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

-

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

Nice challenge ! I think I got it, and here are the main differences with your code:

• For the prime generator, I used the best pure python code from this thread. Apparently, it is way faster to use numpy but since I don't know if your allowed to use third party library, I chose to make my code pure python:

def primes(n):
sieve = [True] * (n/2)
for i in xrange(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 xrange(1,n/2) if sieve[i]]

• Binary search: I first used the native python module bisect to perform the binary search. But afterward I realized it is even simpler (and faster) to use a set of primes (see this page about time complexity):

MAX = 10**6
PRIMES = set(primes(MAX))

• For the main loop, I made it really simple. First of all I use an output file because printing tons of data in the console makes your program really slow and it is not workable after the execution is done. Then I just loop over my 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. I tried not to duplicate any code in order to make it simple and fast:

with open("output.txt", "w") as f:
score = 0
for i,p in enumerate(PRIMES):
s = str(p)
r = int(s[::-1])
if r>p and r in PRIMES:
f.write(s+"\n")
score += 1


This is the result:

>>> Score = 5592 in 0.109 s


And here is the full code:

from time import time
t = time()

# Define prime generator
def primes(n):
sieve = [True] * (n/2)
for i in xrange(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 xrange(1,n/2) if sieve[i]]

# Compute primes
MAX = 10**6
PRIMES = set(primes(MAX))

# Write results in a file
with open("output.txt", "w") as f:
score = 0
for i,p in enumerate(PRIMES):
s = str(p)
r = int(s[::-1])
if r>p and r in PRIMES:
f.write(s+"\n")
score += 1

# Display score
print("Score = {} in {:.3f} s".format(score, time()-t))

-

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)

-

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)

-

## protected by 200_success♦Apr 1 '14 at 9:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.