Rubyで素数判定 - ウィルソンの定理
以前Pythonで書いたコードは、計算にすごく時間がかかっていました。
8桁の素数判定が20分かかってもできないほど。
そこで、今回は計算方法を変えてRubyで実装しました。
以下が、そのコードです。
前回のコードでは、階乗を最後まで行ってから剰余計算を行っていましたが、
今回は乗算1回ごとに剰余計算を行うようにしました。
その結果、演算速度が著しく上昇しました。
このコードなら、8桁の素数も10秒ほどで判定できます。
# Input
print "number : "
num = gets.to_i
sum = 1
(1..num-1).each do |n|
sum *= n
sum %= num
end
sum += 1
# Output Result
if sum % num == 0
print "\nPrime number.\n"
else
print "\nComposite number.\n"
end