Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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)
share|improve this question
    
For generating primes, see Sieve of Eratosthenes - Python –  Janne Karila Mar 31 at 17:04
    
Why wait until you've compiled the entire list to start outputting? –  kojiro Mar 31 at 19:20
1  
@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 at 22:10
1  
@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 at 15:42
1  
@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 at 19:32

5 Answers 5

up vote 6 down vote accepted

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
share|improve this answer

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.

share|improve this answer
    
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 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 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 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 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 sundaram3(max_n):
        numbers = range(3, max_n+1, 2)
        half = (max_n)//2
        initial = 4
        for step in xrange(3, max_n+1, 2):
            for i in xrange(initial, half, step):
                numbers[i-1] = 0
            initial += 2*(step+1)
            if initial > half:
                return [2] + filter(None, numbers)
    
  • 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(sundaram3(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.718 s

And here is the full code:

from time import time
t = time()

# Define prime generator
def sundaram3(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4
    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)
        if initial > half:
            return [2] + filter(None, numbers)

# Compute primes
MAX = 10**6
PRIMES = set(sundaram3(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))
share|improve this answer

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)
share|improve this answer

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)
    
share|improve this answer

protected by 200_success Apr 1 at 9:05

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.