nurse https://blog.hatena.ne.jp/nurse/ なるせにっき https://naruse.hateblo.jp/ なんか、エラトステネスの篩を用いていると言いつつ試行割算法を混同していたり、エラトステネスの篩を用いつつもハッシュを使ったりして速度を落としている例が多いような。エラトステネスの篩では加算しか使わない。だから速い、圧倒的に。 追記: もっとも、肝は真偽値テーブルを使うことで、一つ一つ候補を見なくて済む、篩の手法だから。割り算を排除すれば速くなるかというと、そうでもない。 (割り算がある所は高速化の余地があるというのは確かだけど) def sieve_simple(max) primes = [] table = Array.new(max+1).fill(true, 2); mid = Mat… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnaruse.hateblo.jp%2Fentry%2F20060618%2F1150589528" title="エラトステネスの篩 - なるせにっき" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2006-06-18 09:12:08 rich https://naruse.hateblo.jp/entry/20060618/1150589528 1.0 100%