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
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
```