Project Euler Solution 47: Distinct primes factors

With Problem 47: Distinct primes factors we have another prime factor problem to solve.

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 each. What is the first of these numbers?

We use the get_prime_factors function from Solution 5: Smallest multiple to give us the prime factors and their multiplicities. We only take the unique factors here and discard the rest. We wrap it into a cache such that we don't recompute the results when we revisit a number.

@functools.lru_cache(4)
def get_num_unique_factors(number: int) -> set[int]:
    return len(set(get_prime_factors(number).keys()))

Then we just iterate through all the numbers. If any of the four subsequent numbers doesn't have exactly four divisors, we continue to the next one.

def solution() -> int:
    for i in itertools.count(1):
        if all(get_num_unique_factors(i + n) == 4 for n in range(4)):
            return i

This took 16 s to run. The prime numbers are cached, so that cannot be it. Perhaps the creation of the dictionary takes a bit of time. One could perhaps abort earlier when there there are more than four factors.