Project Euler 37: Truncatable Prime

I read the problem statements from both of the problems on hackerrank and project euler.
The problem at hackerrank is more general and has specific constraints. Here is the problem statement:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797 , 797, 97, and 7. Similarly we can work from right to left: 3797 , 379, 37, and 3. Find the sum of primes that are both truncatable from left to right and right to left below N. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

The constraints for N is 100 <= N <= 10^6

Solution:
The problem statement is pretty clear about what we want to do. Basically, we call a number prime truncatable if

• The number is at least 2 digits
• we continuously remove digits from left to right and the results are prime
• we continuoulsy remove digits from right to left and the results are prime

We are asked to find the sum of truncatable prime numbers below any N?
The first idea that comes to find is to iterate every odd number (2 is the only prime even number) starting from 11 up to (N - 1) and checking if the number is truncatable.
This idea roughly translates to:

sum = 0
 for i in range(11, n, 2): 
     if all[i]:
         if is_truncatable(i):
             sum += i

Don’t worry about the function is_truncatable(). We’ll be implementing it in a while.
How efficient is the code? This naive code gets TLE. We’re simply bruteforcing for all the odd numbers. Do we actually need all these computations? Or, is there a better way to reduce computations?
Let’s think for a while… What if we can generate all the prime numbers below N beforehand and check for just the prime numbers as the number has to be prime first to be a truncatable prime number?
The best method to generate prime numbers is using the sieve. I'll be using Sieve of Eratosthenes .
Suppose, we have to generate all the prime from 1 to 120.
The basic idea of the sieve of erasthonses is:

• Make an array of size 121(0 Based Indexing).
• Mark all the numbers as prime initially.
• Strikeout all the multiples of 2 by marking them as non-prime.
• Similarly, strike out all the multiples of 3 and so on
• Finally, we’ll get an array of boolean value.

See the below visualization from Wikipedia.

Translating, the sieve of erasthonses is straightforward.

MAX = 1000000
prime = [True] * (MAX + 1)

def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False

Let’s revisit the _istruncatable() function and try to implement the code.

• Start from a number N
• Remove digit from left one by one
• After removing, if the number is nonprime then immediately return false.
• Else continue removing digits until no digits are left.

Use the same logic for removing digit from right by one. This translates to:

def is_truncatable(n):
    quo = n
    rev = 0 
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        # eg: For n = 3797
        # These pairs are checked 
        # 7 3797
        # 97 379
        # 797 37
        # 3797 3
        # print(reverse_digits(rev), quo)

        # If both of the pairs are prime continue
        if prime[reverse_digits(rev)] and prime[quo]:
            quo //= 10
            continue

        # Else immediately return false
        return False
    # If none of the pairs fails, it is a truncatable prime
    return True

If it doesn't make sense, you can 2 passes or use str() and int() builtins. We need to implement _reversedigits() function as:

def reverse_digits(n):
    quo = n 
    rem = 0 
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        quo //= 10;
    return rev

Here is our final code :

#Author: Bishal Sarang
 
MAX = 1000000
 
prime= [True] * (MAX + 1)
 
# Reverse a number 
# 123 -> 231
def reverse_digits(n):
    quo = n 
    rem = 0 
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        quo //= 10;
    return rev
 
 
def is_truncatable(n):
    quo = n
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        # eg: For n = 3797
        # These pairs are checked 
        # 7 3797
        # 97 379
        # 797 37
        # 3797 3
        # print(reverse_digits(rev), quo)
 
        # If both of the pairs are prime continue
        if prime[reverse_digits(rev)] and prime[quo]:
            quo //= 10
            continue
        
        # Else immediately return false
        return False
    
 
    # If none of the pairs fails, it is a truncatable prime
    return True
 
 
def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False
        
 
def main():
    sieve()
    sum = 0;
    n = int(input())
    
    # For all the odd numbers starting from 11 to n - 1
    # If it is a prime, then check for truncatability
    for i in range(11, n, 2): 
        if prime[i]:
            # If truncatable prime
            # Increase the sum
            if is_truncatable(i):
                sum += i
    
    print(sum)
 
if __name__ == "__main__":
    main()

Here is the code that uses string to int and int to string conversion.

#Author: Bishal Sarang

MAX = 1000000
prime= [True] * (MAX + 1)

def is_truncatable(n):
    s = str(n)
    t = s[::-1]
    # If none of the pairs fail, it is a truncatable prime
    return all((prime[int(s[:j])] and  prime[int(t[:j][::-1])] for j in range(1, len(s) + 1)))
 

def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False
        

def main():
    sieve()
    sum = 0;
    n = int(input())
    # For all thhe odd numbers starting from 11 to n - 1
    # If it is a prime, then check for truncatability
    for i in range(11, n, 2): 
        if prime[i]:
            # If truncatable prime
            # Increase the sum
            if is_truncatable(i):
                sum += i
    print(sum)

if __name__ == "__main__":
    main()