Deux nombres consécutifs, chacun avec deux facteurs premiers différents, apparaissent en premier:
14 = 2 × 7
15 = 3 × 5
Trois nombres consécutifs, chacun avec trois facteurs premiers différents, apparaissent en premier:
644 = 2**2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
Trouvez quatre nombres consécutifs, chacun avec quatre facteurs premiers différents qui apparaissent en premier. Quels sont les premiers nombres? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
J'ai créé une fonction get_prime_factor_list qui fait une liste de nombres premiers de chaque nombre jusqu'au nombre spécifié max. Cette fonction, par exemple, crée une liste comme celle-ci:
6→[2,3]
8→[2]
12→[2,3]
En utilisant cela, j'ai recherché le premier nombre dans lequel le nombre d'éléments dans la liste ci-dessus est de 4 ou plus dans une rangée de 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