Count distinct primes, discarding palindromes, in under 2 seconds

Question

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( ≤ 10¹⁵ ). Don't print more than 10⁶ 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)

Answer 1

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
            prime_numbers.add(new_prime)
            for k in range((2*j+6)*j+3, len(sieve), new_prime):
                sieve[k] = False
    return prime_numbers

Answer 2

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.

Answer 3

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

Answer 4

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
            prime_numbers.add(new_prime)
            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)

Answer 5

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)