Project Euler Problem 47: Distinct Primes Factors¶
The source code for this problem can be found here.
Problem Statement¶
The first two consecutive numbers to have two distinct prime factors are:
The first three consecutive numbers to have three distinct prime factors are:
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
Solution Discussion¶
The obvious approach to this problem is to increment through integers, factor them, and identify a run of four integers, each with four unique prime factors. Even those these integers are quite small, factoring is very expensive. It would be good to avoid repetitive factoring.
A slight tweak on prime sieving will actually work very well for this problem. During traditional prime sieving we build a list of primes by invalidating composite numbers. Each composite will be marked by each of its prime divisors. So, rather that simply mapping an integer to a boolean indicating “prime or not”, we can store a count of the number of prime numbers that divide each composite number.
Once sieving has completed, we may search for a run, four long, of integers with a count of four prime divisors.
There is actually one simple improvement that can be made on this scheme. Note that sieving occurs by iterating over the integers in ascending order, and that as we process each integer we know any smaller prime divisors have been accounted for. Further, an integer is only divisible by smaller prime factors. This means, that as we process each integer, we know that we have already considered all prime divisors of that integer. Therefore, we can search for the run of four successive integers with four distinct prime divisors while sieving occurs.
Solution Implementation¶
def solve():
""" Compute the answer to Project Euler's problem #47 """
target = 4 # number of prime factors and successive integers
limit = 150000 # arbitrary upperbound on the search, found by trial and error
n_prime_divisors = [0] * limit # the number of prime divisors of each integer considered
run_length = 0 # length of the current run of valid integers
for n in range(2, limit):
if n_prime_divisors[n] == 0:
# n is prime, sieve out multiples of n
for m in range(2 * n, limit, n):
n_prime_divisors[m] += 1 # m is divisible by n (prime)
run_length = 0 # n is invalid, reset our run counter
elif n_prime_divisors[n] == target:
run_length += 1 # n is valid, increment our run counter
else:
run_length = 0 # n is invalid, reset our run counter
if run_length == target:
return n  target + 1 # we've found the smallest target run
expected_answer = 134043

solutions.problem47.
solve
()¶ Compute the answer to Project Euler’s problem #47