Home > Project Euler, python > Problem euler #37

Problem euler #37

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.

Analisi:
In modo molto simile al problem euler 35, saltiamo i numeri comprendenti le cifre:0,4,6,8, altrimenti durante il troncamento, con queste cifre finali avremmo dei numeri non primi, poichè multipli di 5 e 2.
Ho tenuto 2 e 5 poichè singolarmente, sono primi.

python:

import time
ts = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True

def is_sliced_prime(n, side='left'):
    if '0' in str(n) or '4' in str(n) or '6' in str(n) or '8' in str(n):
        return False # 5 and 2 are primes when alone
    while len(str(n)) > 0: 
        if is_prime(int(n)):
            if side == 'left': n = str(n)[1:] # left to right
            else: n = str(n)[:-1] # right to left
        else:
            return False
    return True

elevens = []
for i in xrange(11, 10**6, 2):
    if is_sliced_prime(i, 'left') and is_sliced_prime(i, 'right'):
        elevens.append(i)
    if len(elevens) == 11:
        break
print sum(elevens)
print time.time() - ts
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: