Two consecutive numbers, each with two different prime factors, first appear:
14 = 2 × 7
15 = 3 × 5
Three consecutive numbers, each with three different prime factors, first appear:
644 = 2**2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
Find four consecutive numbers, each with four different prime factors that appear first. What are the first numbers? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
I created a function get_prime_factor_list that creates a list of divisors of each number up to the specified number max. This function, for example, creates a list like this:
6→[2,3]
8→[2]
12→[2,3]
Using this, I searched for the first number in which the number of elements in the above list is 4 or more in a row of 4.
# coding: utf-8
import math
from mymath import get_prime_boolean
def get_prime_factor_list(max):
bool = get_prime_boolean(max)
ret = [ [] for i in range(max+1)]
for p in range(max+1):
if bool[p]:
for j in range(p*2,max,p):
ret[j] += [p]
return ret
def main():
# TPF stands for a threshold of number of prime factors.
# TCI stands for a threshold of number of concecutive integers
MAX, TPF, TCI =10**6, 4, 4
prime_factor_list = get_prime_factor_list(MAX)
ans = []
for i in range(MAX):
if len(prime_factor_list[i]) >= TPF:
ans.append(i)
if len(ans) == TCI:
break
else:
ans = []
print ans[0]
main()
Recommended Posts