The first two consecutive numbers to have two distinct prime factors are:
\begin{align} 14 &= 2 \times 7\\ 15 &= 3 \times 5. \end{align}The first three consecutive numbers to have three distinct prime factors are:
\begin{align} 644 &= 2^2 \times 7 \times 23\\ 645 &= 3 \times 5 \times 43\\ 646 &= 2 \times 17 \times 19. \end{align}Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
Like with the previous problem, my solution to this problem adapts a prime sieve.
For all \(m\) less than some cap \(C\), let \(p_n[m]\) be the number of distinct prime factors of \(m\) that are less than or equal to \(n\), with initial condition \(p_1[m] = 0\). Also, let \(s_n\) be the number of consecutive integers ending with \(n\) that have exactly four distinct prime factors, with initial condition \(s_1 = 0\). The outer loop iterates over \(n\).
If \(p_{n-1}[n] = 4\), then \(s_n = s_{n-1} + 1\); and if \(s_n = 4\), the solution is \(n-3\). If \(p_{n-1}[n] \neq 4\), then \(s_n = 0\). If \(p_{n-1}[n] = 0\), then \(n\) is prime, and so \(p_n[kn] = p_{n-1}[kn] + 1\) for all integer \(k\). If \(n\) is not prime or does not divide \(m\), then \(p_n[m] = p_{n-1}[m]\).
def p47():
C = 10**6 # it's enough
s = 0
p = [0 for m in range(C)]
for n in range(2, C):
if p[n] == 4:
s += 1
if s == 4:
return n-3
else:
s = 0
if p[n] == 0:
for m in range(n, C, n):
p[m] += 1