Home > Project Euler, python > Problem euler #41

Problem euler #41

'''
We shall say that an n-digit number is pandigital if it makes use of all
the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital
and is also prime.

What is the largest n-digit pandigital prime that exists?
'''

Analisi:

I numeri pandigitali di 9 cifre, sono tutti divisibili per 3, quindi non
primi. Infatti la somma delle loro cifre dà 45, che è divisibile per 3.
123456789 = 45

I numeri pandigitali di 8 cifre, anche, dal momento che le cifre sommate,
danno 36 che è ancora divisibile per 3.

I numeri primi li troviamo nei pandigitali da 7. Quindi cicleremo su tali numeri.

Per farlo creo un generatore di numeri pandigitali di 7 cifre.
Poi ciclando su di esso controllerò quali di questi sonon primi.
Il più grande, è il nostro risultato.

Un ulteriore filtro in questi numeri, consiste nell’escludere i pandigitali pari
(%2 == 0) inquanto non primi.

In python il tutto si traduce così:

import time
import itertools as it

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 pan_generator():
    for i in it.permutations(range(1,8)):
        # 8-digit and 9-digit pandigital numbers,
        # are all divisible by 3, so not primes.
        # check the 7-digit pandigital numbers
        comb = ''
        for n in i:
            comb += (str(n))
        if int(comb) % 2 != 0: yield int(comb)
    
maxpp = 2143

for n in pan_generator():
    if is_prime(n):
        if n > maxpp: maxpp = n

print "problem euler 41: {} \nelapsed time: {}sec".format(maxpp, 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: