Home > Project Euler, python > Problem euler #35

Problem euler #35

The number, 197, is called a circular prime because all rotations
of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Analisi:
da wikipedia sappiamo che i numeri non devono comprendere le cifre 0,2,4,5,6,8, altrimenti
durante la rotazione, una volta arrivati in ultima posizione renderebbero il numero ottenuto
divisibile per 2 o per 5, quindi non primo.

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_circ_prime(n):
    if '0' in n or '2' in n or '4' in n or '6' in n \
       or '5' in n or '8' in n: return False
    for d in [int(n[i+1:] + n[:i+1]) for i in range(len(n))]:
        if not is_prime(d):
            return False
    return True

circ_primes = [x for x in xrange(3, 10**6, 2) if is_circ_prime(str(x))]

print len(circ_primes) + 2 # excluded 2 in xrange and 2 is_circ_prime func
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: