Problem 47

Solution to Problem 47. Written in Python.

Problem: 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 prime factors. What is the first of these numbers?

from problems.euler_lib import euler_lib as lib

primes = lib.eratosthenes_sieve(1000)

candidates = [n for n in xrange(1, 150000) if len(lib.prime_factorization(n, primes)) == 4]

i = 0
candidates_len = len(candidates)
while i < candidates_len - 3:
    first = candidates[i + 1] - candidates[i]
    second = candidates[i + 2] - candidates[i + 1]
    third = candidates[i + 3] - candidates[i + 2]

    if first == 1 and second == 1 and third == 1:
        print candidates[i]

    i += 1