読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

Project Euler 204

PE

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以下のモノだけで構成されているかを調べた.