Archivio

Posts Tagged ‘euler’

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)
Categorie:Project Euler, python Tag: ,

project euler 89

27 Luglio 2016 Commenti chiusi

Qui il testo del problema 89

Si deve calcolare il totale dei caratteri risparmiati durante la semplificazione dei numeri romani.
Ci ho messo un po’ a capirlo e continuavo a calcolare il totale dei caratteri della lista corretta….

import time


def filter_romans(path):
    with open(path) as inputfile:
        romans = [num.strip() for num in inputfile]
    startchr = sum([len(r) for r in romans])

    for bad, correct in [("VIIII", "IX"), ("IIII", "IV"),
                         ("LXXXX", "XC"), ("XXXX", "XL"),
                         ("DCCCC", "CM"), ("CCCC", "CD"),]:
        for roman in romans:
            index = romans.index(roman)
            if bad in roman:
                romans[index] = roman.replace(bad, correct)
    return startchr - sum([len(r) for r in romans])


if __name__ == "__main__":
    start = time.time()
    result = filter_romans(r"p089_roman.txt")
    print "euler 89: %s\nElapsed time %ss." % (result, time.time() - start)
Categorie:Project Euler, python Tag: ,