Project Euler #47

47.py

#!/usr/bin/env python

from libeuler import is_prime

def prime_factors(n, P):
    r = []
    t = n
    while True:
        if t == 1:
            break
        for p in P:
            if t % p == 0:
                r += [p]
                t /= p
                break
    return r

if __name__ == '__main__':
    n = 10
    primes = filter(lambda x: is_prime(x), range(1000000))
    while True:
        l1 = len(set(prime_factors(n, primes)))
        l2 = len(set(prime_factors(n+1, primes)))
        l3 = len(set(prime_factors(n+2, primes)))
        l4 = len(set(prime_factors(n+3, primes)))

        if l1 == 4 and l2 == 4 and l3 == 4 and l4 == 4:
            print n
            break

        print "%d -> %d %d %d %d" % (n, l1, l2, l3, l4)
        n += 1