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.
