Project Euler 39

Sat, Dec 29, 2007

After a long time , but here is another project euler problem that I worked on.

This one was quite fun.

Problem:-

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 the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Solution:-

Again its a brute force ( takes a while to get the last prime) ,

I use a generator I found online to get the list of primes and then check if it left and right truncatable.

import time
from itertools import ifilter, count

def isPrime(n):
    if n == 1:
        return False
    
    i = n - 1
    while i > 1:
        rem = n % i
        if rem == 0:
            return False
        else:
            i = i - 1
    return True

def truncateLeft(num):

    k = num

    while k != 0:
        k /= 10
        if not isPrime(k):
            return False
    return True


def truncateRight(num):
    k = num

    while k != 0:
        k %=(10**(len(str(k))-1))
        if not isPrime(k):
            return False
    return True

def sieve():
    g = count(2)
    while True:
        prime = g.next()
        yield prime
        g = ifilter(lambda x, prime=prime: x % prime,g)




candidates = []

t = time.time()

primes = sieve()
start = primes.next()

while len(candidates) != 11:
    if truncateLeft(start) and truncateRight(start) and start > 7:
        candidates.append(start)
        print str(start) + " has been added"
    start = primes.next()

print sum(candidates)   
print time.time() - t

Project Euler 39

Comments