Home > Project Euler, python > Project Euler 87

Project Euler 87

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^4

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
import time


def is_prime(num):
    if num == 2:
        return True
    if num % 2 == 0 or num <= 1:
        return False
    sqr = int(num ** 0.5) + 1
    for divisor in xrange(3, sqr, 2):
        if num % divisor == 0:
            return False
    return True

def euler87(limit):
    """a**2 + b**3 + c**4"""
    results = set()
    primes = [x for x in xrange(2, int(limit ** 0.5))
              if is_prime(x)]
    for p4 in primes:
        for p3 in primes:
            partial = p4**4 + p3 ** 3
            if partial >= limit:
                break
            for p2 in primes:
                tot = p2 ** 2 + partial
                if tot >= limit:
                    break
                results.add(tot)
    return len(results)


if __name__ == "__main__":
    start_time = time.time()
    print "euler 87: {} \nelapsed time: {}s".format(
        euler87(50000000), time.time() - start_time)
Categorie:Project Euler, python Tag:,
  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: