Project Euler 47

問題

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7
15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 2**2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047

回答

指定された数maxまでの各数の約数の素数のリストを作る関数get_prime_factor_listを作った。この関数は、たとえば、次のようなリストを作成する。

6→[2,3]
8→[2]
12→[2,3]

これを使って、上記リストの要素数が4以上となるような数が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()