Warning: Creating default object from empty value in /membri/bancaldo/wp-content/plugins/paged-comments/paged-comments.php on line 31
bancaldo™ » Project Euler 87
Home > Project Euler, python > Project Euler 87

Project Euler 87

8 settembre 2016
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: ,
I commenti sono chiusi.