素数を数える作業。

最近落ち着かない、そういう時は！
素数を数えるんだ！！！１１１１１１１１

Rubyコード

def mp(p)
	ans = 4

	(p-2).times do
		ans = ans ** 2 - 2
	end
	
	ans
end

def MersenneNum(n)
	2**n-1
end

1.upto(100) do |i|
#メルセンヌ数を求める
	mnb = MersenneNum(i)
	
#Lucas-Lehmerテストの補助式を解く
	mpb = mp(i)

#Lucas-Lehmerテストを評価する
#補助式で求めた数に対する、評価したいメルセンヌ数の剰余が、０である場合、
#そのメルセンヌ数はメルセンヌ素数である。
	if(mpb % mnb == 0)
		puts "M#{i} is Prime Number."
		puts "M#{i} = #{mnb}"
	end
end

ここで数えているのは、正確にはメルセンヌ素数。

メルセンヌ数 - Wikipedia

一瞬でカタルディさんのM19くらいは出てくる・・・が、初算出年1588年かよ！ｗｗ

PS K:\ruby_sample> ruby lucas.rb
M1 is Prime Number.
M1 = 1
M3 is Prime Number.
M3 = 7
M5 is Prime Number.
M5 = 31
M7 is Prime Number.
M7 = 127
M13 is Prime Number.
M13 = 8191
M17 is Prime Number.
M17 = 131071
M19 is Prime Number.
M19 = 524287

これ以上やるととんでもない巨大数になりそうなので、別の方法を考えないといけないと思う。
多倍長ライブラリをCellか、CUDAで実装してみたいなー

#Rubyってすごいよねー、速度は仕方ないとして、こんな簡単に巨大数を扱えるのだから。