素数リストを作ってくれるプログラム
Twitter で区切りのいいつぶやきのときに素数をつぶやいていたので、どうやっていたかの種明かし。
単純にプログラムを書いて動かしてただけなんですけどね。
そのプログラムは以下のようなもの。与えた数字までの素数を全て配列にして返してくれます。n 番目の素数が知りたければその番号にアクセスするだけ。アルゴリズムは原始的なものですけど、数値抜けを防ぐためにそうしてます。
#判定用メソッド。素数ならば true,でなければ false #引数は判定する数値 n と素数リスト prime def judge( n, prime ) i = 2 p = prime[i] while p * p <= n return false if n % p == 0 i += 1 p = prime[i] end return true end #素数リストを作るメソッド #引数 num までの素数リストを作る def prime( num ) prime = [ 2, 3, 5 ] x1, x2 = 7, 5 #素数が出てくる数は 5+6n と7+6n loop{ x1 = x2 + 2 break if num < x1 prime << x1 if judge( x1, prime ) x2 = x1 + 4 break if num < x2 prime << x2 if judge( x2, prime ) } return prime end
相変わらず Ruby で書いてます。C で書いてもいいけどプログラムの本質を理解するためなら Ruby みたいな言語がいいと思う。