Gemma https://blog.hatena.ne.jp/Gemma/ Gemmaの日記 https://gemma.hatenadiary.org/ Haskellなどで人気の1行エラトステネスの篩は、アルゴリズム本来の計算量より遅いらしい。 sieve (p : xs) = p : sieve [x | x <- xs, x ‘mod‘ p > 0] LtU:The Genuine Sieve of Eratosthenes Wikipedia:en:Sieve of Eratosthenes それを受けて、LtUで以下の速いHaskellコードがあった。 primes = 2 : xor [3..] (composites primes) composites (p:ps) = cs where cs = (p*p) : xor (ma… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fgemma.hatenadiary.org%2Fentry%2F20090420%2F1240260347" title=" Gaucheでエラトステネスの篩で素数ストリーム(世間一般のやつより速い) - Gemmaの日記" 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 2009-04-20 05:45:47 rich https://gemma.hatenadiary.org/entry/20090420/1240260347 1.0 100%