61 lines
1.3 KiB
Python
61 lines
1.3 KiB
Python
#!/usr/bin/env python3
|
||
|
||
# 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?
|
||
from typing import List
|
||
|
||
from projecteuler import timing
|
||
|
||
|
||
# Function using a modified sieve of Eratosthenes to count
|
||
# the distinct prime factors of each number.
|
||
def count_factors(n: int) -> List[int]:
|
||
factors = [0] * n
|
||
i = 2
|
||
|
||
while i < n // 2:
|
||
if factors[i] == 0:
|
||
for j in range(i, n, i):
|
||
factors[j] = factors[j] + 1
|
||
i = i + 1
|
||
|
||
return factors
|
||
|
||
|
||
@timing
|
||
def p047() -> None:
|
||
N = 150000
|
||
|
||
factors = count_factors(N)
|
||
|
||
count = 0
|
||
|
||
# Find the first instance of four consecutive numbers
|
||
# having four distinct prime factors.
|
||
for i in range(N):
|
||
if factors[i] == 4:
|
||
count = count + 1
|
||
else:
|
||
count = 0
|
||
|
||
if count == 4:
|
||
res = i - 3
|
||
break
|
||
|
||
print('Project Euler, Problem 47')
|
||
print(f'Answer: {res}')
|
||
|
||
|
||
if __name__ == '__main__':
|
||
p047()
|