Project Euler Problem 047

Statement

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Solution

I did it with a frute-force solution with some performance improvements, any case it takes 2 minutes in a
Pentium-IV.

from CommonFunctions import find_primes_less_than
 
def find_prime_factors(n, primes):
    factores = set()
    index = 0
    while n > 1:
        if n % primes[index] == 0:
            i = 0
            while n % primes[index] == 0:
                n /= primes[index]
                i += 1
            factores.add("%d^%d" % (primes[index], i))
        else:
            index += 1
    return factores
 
if __name__ == '__main__':
    i = 647
    primes = find_primes_less_than(500000)
    factors = {}
    while True:
        if i in factors:
            f1 = factors[i]
        else:
            f1 = factors[i] = find_prime_factors(i, primes)
        while len(f1) != 4:
            i += 1
            if i in factors:
                f1 = factors[i]
            else:
                f1 = factors[i] = find_prime_factors(i, primes)
        if i+1 in factors:
            f2 = factors[i+1]
        else:
            f2 = factors[i+1] = find_prime_factors(i+1, primes)
        if len(f2) != 4:
            i += 1
        else:
            unionSet = f1.union(f2)
            interSet = f1.intersection(f2)
            if len(unionSet) == 8 and len(interSet) == 0:
                if i+2 in factors:
                    f3 = factors[i+2]
                else:
                    f3 = factors[i+2] = find_prime_factors(i+2, primes)
                if len(f3) != 4:
                    i += 2
                else:
                    unionSet = unionSet.union(f3)
                    interSet = interSet.intersection(f3)
                    if len(unionSet) == 12 and len(interSet) == 0:
                        if i+3 in factors:
                            f4 = factors[i+3]
                        else:
                            f4 = factors[i+3] = find_prime_factors(i+3, primes)
                        if len(f4) != 4:
                            i += 3
                        else:
                            unionSet = unionSet.union(f4)
                            interSet = interSet.intersection(f4)
                            if len(unionSet) == 16 and len(interSet) == 0:
                                print("The result is:", i)
                                exit(0)
        i += 1

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License