Project Euler 204

type 以下の素数のリストをエラトステネスの篩で作る.

その素数のみの積で表される数のうちlimit = 10**9を超えない数を数え上げれば良い.

もっとも小さい素数は2であり2**n で始めてlimit を越えるのはn = 30であるので, 素数のリストから30個重複を許さない組み合わせをとり,それの積をとり上の条件を適用する.

for i in range(30+1):

for j in itertools.combinations_with_replacement([2,3,...,97],n):

if 積(j) <= limit: count += 1

else: break

最初はこの方法で行こうとしたのだが, break しちゃいけないことに気づいた. 

積(13,19,19,19,19) > 10**9

だがその次の

積(17,17,17,17,17) < 10**9

であることに気づいた.

combinations_with_replacement()の使い方に気をつけたいと思った.

つまりbreakは不要となるのでこの方法では時間的に無理だと判明した.

結局おこなったことは各1<= n <= 10**9について素因数分解して素因数が1またはtype以下のモノだけで構成されているかを調べた.