Distinct primes factors
Problem 47
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
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.
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?
def run(limit=1000000):
# Might be under a million
# number of prime factors.
factors = [0] * limit
count = 0
num_factors = 4
for i in range(2, limit):
# Only if i is prime factor for the given number, otherwise it's not a prime factor
if factors[i] == 0:
# i is prime
count = 0
val = i
# Mark i as factor to all number < limit
while val < limit:
factors[val] += 1
val += i
elif factors[i] == num_factors:
count += 1
if count == num_factors:
return i - (num_factors - 1) # First number
else:
count = 0