Find the sum of all Truncatable primes below N | Python3 implementation of the above approach ; To check if a number is prime or not ; Sieve of Eratosthenes function to find all prime numbers ; Function to return the sum of all truncatable primes below n ; To store the required sum ; Check every number below n ; Check from right to left ; If number is not prime at any stage ; Check from left to right ; If number is not prime at any stage ; If flag is still true ; Return the required sum ; Driver code
N = 1000005 NEW_LINE prime = [ True for i in range ( N ) ] NEW_LINE def sieve ( ) : NEW_LINE INDENT prime [ 1 ] = False NEW_LINE prime [ 0 ] = False NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT if ( prime [ i ] == True ) : NEW_LINE INDENT for j in range ( i * 2 , N , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def sumTruncatablePrimes ( n ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT num = i NEW_LINE flag = True NEW_LINE while ( num ) : NEW_LINE INDENT if ( prime [ num ] == False ) : NEW_LINE INDENT flag = False NEW_LINE break NEW_LINE DEDENT num //= 10 NEW_LINE DEDENT num = i NEW_LINE power = 10 NEW_LINE while ( num // power ) : NEW_LINE INDENT if ( prime [ num % power ] == False ) : NEW_LINE INDENT flag = False NEW_LINE break NEW_LINE DEDENT power *= 10 NEW_LINE DEDENT if ( flag == True ) : NEW_LINE INDENT sum += i NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT n = 25 NEW_LINE sieve ( ) NEW_LINE print ( sumTruncatablePrimes ( n ) ) NEW_LINE