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