Project Euler 87
8 Settembre 2016
Commenti chiusi
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)
Commenti recenti