Rubyで2^x以上で最小の素数
ちょと必要だったので、そのときのプログラムをメモ。
なぜ計算したかったのか？
xが1〜32までの時の2^x以上で最小の素数が欲しかったんです
ハッシュテーブルの大きさとかによく使うでしょ（そうそれ！
ソース
require 'mathn' (1..32).each{|x| puts lambda{|i| while true break if i.prime? # break if i.prime_division.size == 1 && i.prime_division[0][1] == 1 # break if 'X' * i !~ /\A(XX+)\1+\z/ i = i + 1 end return i }.call(2**x) }
出力
2 5 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101 262147 524309 1048583 2097169 4194319 8388617 16777259 33554467 67108879 134217757 268435459 536870923 1073741827 2147483659 4294967311
解説
素数を求めるためにInteger#prime_divisionを使っています。
prime_divisionは整数を素因数分解するためのメソッドです。
各素因数がいくつあるかを、2次元配列で返してくれます。
irb(main):391:0* (10..30).each{|x| p x.prime_division}
[[2, 1], [5, 1]]
[[11, 1]]
[[2, 2], [3, 1]]
[[13, 1]]
[[2, 1], [7, 1]]
[[3, 1], [5, 1]]
[[2, 4]]
[[17, 1]]
[[2, 1], [3, 2]]
[[19, 1]]
[[2, 2], [5, 1]]
[[3, 1], [7, 1]]
[[2, 1], [11, 1]]
[[23, 1]]
[[2, 3], [3, 1]]
[[5, 2]]
[[2, 1], [13, 1]]
[[3, 3]]
[[2, 2], [7, 1]]
[[29, 1]]
[[2, 1], [3, 1], [5, 1]]
=> 10..30
注意
prime_divisionを使うためにはmathnをrequireしておく必要があります。
require 'mathn'
ちなみに・・
break if 'X' * i !~ /\A(XX+)\1+\z/
break if i.prime_division.size == 1 && i.prime_division[0][1] == 1
と、同じ動きをするようです。（激遅ですがｗｗｗ
とりあえず、メモ。。
参考：第28回 Ruby/Rails勉強会＠関西 に行ってきたよ - はこべにっき ♨
