Zuerst erscheinen zwei aufeinanderfolgende Zahlen mit jeweils zwei verschiedenen Primfaktoren:
14 = 2 × 7
15 = 3 × 5
Zuerst erscheinen drei aufeinanderfolgende Zahlen mit jeweils drei verschiedenen Primfaktoren:
644 = 2**2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
Finden Sie vier aufeinanderfolgende Zahlen mit jeweils vier verschiedenen Primfaktoren, die zuerst erscheinen. Was sind die ersten Zahlen? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
Ich habe eine Funktion get_prime_factor_list erstellt, die eine Liste der Primzahlen jeder Zahl bis zur angegebenen maximalen Anzahl erstellt. Diese Funktion erstellt beispielsweise eine Liste wie folgt:
6→[2,3]
8→[2]
12→[2,3]
Damit suchte ich nach der ersten Zahl, bei der die Anzahl der Elemente in der obigen Liste 4 oder mehr in einer Reihe von 4 beträgt.
# 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