Project Euler Problem 47 Statement
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?
Solution
The algorithm employs a modification of the Sieve of Eratosthenes to track numbers with exactly K prime factors. When examining each number starting from 2, it first checks if that number has K prime factors. If it does, it increments a counter tracking consecutive matches. Once K consecutive numbers are found with K factors each, it prints the first number in that sequence.
After finding a sequence of numbers with the required number of prime factors, we decrement the counter by 1 rather than resetting it. This allows us to keep searching for new sequences that might overlap with our previous find. for example, when K=2 and we find $33 (3\times 11), 34 (2\times 17), 35 (5\times 7),$ and $36 (2^2\times 3^2)$ we would print 33, 34,35 for 3 sequences of 2 consecutive numbers with 2 prime factors.
For prime numbers (those still marked with 0), the algorithm marks all their multiples by incrementing their factor counts. For instance, when processing 2, it adds one factor to 4, 6, 8, and 10. Then when processing 3, it adds another factor to numbers like 6, 9, 12, and 15. Through this process, composite numbers accumulate factors from their prime divisors – for example, 12 gets one factor from 2 and another from 3. Then cnt is reset to zero; the chain has been broken.
This sieve approach is about 25x faster than finding the prime factors for each number.
Walkthrough
Let's have a peek at the process of building the prime factor list, f[].
# Initial setup K = 2 N = 15 + K # N becomes 17 to handle edge cases f = [0] * N # f = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] cnt = 0 # counter for consecutive numbers # Let's go through iterations: # n = 2 (first prime) # f[2::2] gets +1, marking all multiples of 2 # f becomes: [0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16] (indices) # n = 3 # f[3::3] gets +1, marking all multiples of 3 # f becomes: [0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1] # n = 4 (has f[4]=1, not prime, skip) # n = 5 (prime) # f[5::5] gets +1 # f becomes: [0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 1, 1] # n = 6 (has f[6]=2, matches K!) # cnt becomes 1 # n = 7 (prime) # f[7::7] gets +1 # f becomes: [0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 1, 1]
Let's check what happened for some specific numbers:
- f[6] = 2 because 6 = 2 × 3 (two prime factors)
- f[8] = 1 because 8 = 23 (one unique prime factor)
- f[10] = 2 because 10 = 2 × 5 (two prime factors)
- f[12] = 2 because 12 = 22 × 3 (two unique prime factors)
When we hit n=6, it had exactly K=2 factors, so cnt became 1. But since we never found another consecutive number with exactly 2 factors (would need f[7]=2), cnt got reset to 0.
Let's continue our example to find the first solution. We'll extend our range to find 14 and 15.
# Continuing from before, now focused on numbers 13-15: # n = 13 (prime) # f[13::13] gets +1 # Number 13 marks its multiples, but first multiple is beyond our range # n = 14 # f[14] = 2 (because it was marked by 2 and 7) # cnt becomes 1 (found first number with exactly 2 factors) # n = 15 # f[15] = 2 (because it was marked by 3 and 5) # cnt becomes 2 (found second consecutive number with 2 factors) # Since cnt == K (which is 2), we print n-K+1 # This prints 14 (calculated as 15-2+1)
Let's verify why 14 and 15 are our answer:
14's prime factorization:
- 14 = 2 × 7
- Has exactly 2 distinct prime factors ✓
15's prime factorization:
- 15 = 3 × 5
- Has exactly 2 distinct prime factors ✓
14 gets printed because it's the first number in the sequence of 2 consecutive numbers that each have exactly 2 distinct prime factors.
HackerRank version
HackerRank Project Euler 47: Find $K$ consecutive integers to have exactly $2\le K\le 4$ distinct prime factors where the first integer is $20\le N\le 2\times 10^6$.
Python Source Code
N, K = map(int, input().split())
N+= K
f, cnt = [0]*N, 0
for n in range(2,N):
if f[n] == K:
cnt+=1
if cnt == K:
print(n-K+1)
cnt-= 1
else:
cnt = 0
if f[n]==0: f[n::n] = [c+1 for c in f[n::n]] Last Word
Some interesting data from this program.
| Number of factors | Sequence Length | Starting number |
|---|---|---|
| 2 | 2 | 14 |
| 2 | 3 | 20 |
| 2 | 4 | 33 |
| 2 | 5 | 54 |
| 2 | 6 | 91 |
| 2 | 8 | 141 |
| 3 | 2 | 230 |
| 3 | 3 | 644 |
| 3 | 4 | 1308 |
| 3 | 5 | 2664 |
| 3 | 6 | 6850 |
| 3 | 7 | 10280 |
| 3 | 8 | 39693 |
| 3 | 9 | 44360 |
| 3 | 10 | 48919 |
| 3 | 11 | 218972 |
| 3 | 14 | 526095 |
| Number of factors | Sequence Length | Starting number |
|---|---|---|
| 3 | 15 | 17233173 |
| 3 | 16 | 127890362 |
| 4 | 2 | 7314 |
| 4 | 3 | 37960 |
| 4 | 4 | Answer |
| 4 | 5 | 357642 |
| 4 | 7 | 1217250 |
| 4 | 8 | 14273478 |
| 4 | 9 | 44939642 |
| 4 | 10 | 76067298 |
| 4 | 11 | 163459742 |
| 5 | 2 | 254540 |
| 5 | 3 | 1042404 |
| 5 | 4 | 21871365 |
| 5 | 5 | 129963314 |
| 6 | 2 | 11243154 |
| 6 | 3 | 323567034 |