Project Euler #37: Truncatable primes

  • + 0 comments

    Python

    N = int(input())
    primes = {2, 3, 5, 7}
    truncatable_primes = []
    
    def is_prime(n):
        if n in primes:
            return True
        elif n == 1:
            return False
        elif n % 2 == 0:
            return False
        else:
            # Check for divisibility up to the square root of n
            for i in range(3, int(n**0.5) + 1, 2):
                if n % i == 0:
                    return False
            return True
    
    def is_truncatable_prime(n):
        num_strL = num_strR = str(n)
        
        while len(num_strL) > 0:
            curr = int(num_strL)
    				
            if is_prime(curr):
                primes.add(curr)
                num_strL = num_strL[1:]
            else:
                return False
        
        while len(num_strR) > 0:
            curr = int(num_strR)
    				
            if is_prime(curr):
                primes.add(curr)
                num_strR = num_strR[:-1]
            else:
                return False
                
        return True
    
    for i in range(11, N):
        if is_prime(i):
            primes.add(i)
            if is_truncatable_prime(i):
                truncatable_primes.append(i)
    
    # print(truncatable_primes)
    print(sum(truncatable_primes))