汎用的で省メモリかつかなり速い素数無限列挙 - 名古屋で数学するプログラマ(仮)
台風凄かったですね。私の住んでいる地域では、夕方頃に風雨ともかなり強かったのですが、今はもうだいぶ落ち着いてきちゃいました。 さてさて。昨日の記事の続きです。 まずはPrime::A2Generatorの説明、その前に、その元になっているメモ: 上限を決めずに素数を生成の高速化(Ruby版)のPrimeGeneratorの解説から。 log.ttsky.net の PrimeGenerator の解読 大元の記事は、メモ: 素数の逐次生成(Ruby版) v3。たどればもっと元があるようですけれど取り敢えず。ここに書かれているMyPrimeクラスの高速化を図った究極形がこっちの記事のPrimeGeneratorクラス*1。 このクラスが素数を列挙するアルゴリズム（succメソッドの中身）は、読み解くと以下の通り*2： 取り敢えず最初に2を返す。 2回目以降は2以上の数を2つずつ順に判定： 最
汎用的でけっこう速い素数無限列挙 - 名古屋で数学するプログラマ(仮)
二週間ぶりです。風邪引いてました。二週間かかってようやく落ち着きました。この時期の夏風邪ってば以下略。 さてさて、今日から暫く「素数列挙」の話をします。 Ruby1.9 の素数列挙メソッド Ruby1.9には、素数列挙・素数判定・素因数分解を一手に扱う素数ライブラリが用意されています。 このブログでも素数列挙する時とかに何の説明もなく使ってました。 require 'prime' Prime.each {|pr|puts pr} # => 2 # => 3 # => 5 # => 7 # => 11 # => …（以降無限に列挙） これ、割と速いです。というか結構速いです。 python+素数列挙でググるとよく出てくる、こんなサンプル from itertools import ifilter, count def prime_generator(): g = count(2) while
エラトステネスのふるいをコンパクトにする方法 - Smalltalkのtは小文字です
関連エントリー： 100までの整数から素数を列挙せよ…を Squeak の Smalltalk で Smalltalk のオーソドックスな方法で。 100までの整数から素数を列挙せよ…を Smalltalk-76 で Smalltalk の祖先で。 100までの整数から素数を列挙せよ…を Smalltalk-72 で Smalltalk の祖先の祖先で。 100までの整数から素数を列挙せよ…を bitblt で ビット演算ルーチンで。 100までの整数から素数を列挙せよ…を Squeak の eToys で タートルグラフィックスで。 素数を列挙するにあたって、エラトステネスのふるいは比較的高速で有効です。たとえば、404 Blog Not Found:LLR2006 - 1,000,000(番目|まで)の素数 で、いくつかの言語で例示されているのとほぼ同じことをする Squeak を使っ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
