Home > Project Euler, python > Problem euler #50

Problem euler #50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below
one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime,
contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most
consecutive primes?

Analisi:

Con un ordine di grandezza di un milione di primi, ho optato per un generatore.
Ho creato anche una lista di numeri primi limitata, da usare come punto di partenza
per i generatori di primi.
In sostanza ciclo sui vari punti di partenza per originare i miei generatori.
Prima utilizzo un generatore con range (2, limite max), poi range (3, limite max),
range (5, limite max) e così via.
Da ogni generatore, sommo tutti i primi fino al limite stabilito (10**6).
Quando la somma è un primo ed è l’ultima prima del limite, memorizzo il numero
di primi che ho sommato ed il valore della somma ottenuta, su due variabili
esterne ai cicli innestati.
Poi proseguo con un nuovo generatore che parta da un primo maggiore.
Alla fine dei cicli for, avrò la massima somma per il numero massimo di
primi consecutivi.
Il tiro dei limiti massimi, è stato aggiustato una volta trovato il risultato.
Potrebbe essere affinato ancora, ma il tempo di esecuzione è più che soddisfacente.

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

limit = 10**4
start = [x for x in xrange(1, 10) if is_prime(x)]

maxsum = cmax = 0
for s in start:
    primes = (x for x in xrange(s, limit) if is_prime(x))
    count = 0
    psum = 0
    for p in primes:
        psum += p
        count += 1
        if is_prime(psum) and psum < 10**6:
            if psum > maxsum:
                maxsum, cmax = psum, count

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