結果

問題 No.308 素数は通れません
ユーザー kura07
提出日時 2015-12-01 02:16:06
言語 Ruby
(3.4.1)
結果
AC  
実行時間 93 ms / 1,000 ms
コード長 873 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-11-27 18:06:28
合計ジャッジ時間 12,078 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 107
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

require 'prime'
class Integer
    def miller_rabin_prime?(k=100)
        n = abs
        return true if n == 2
        return false if n < 2 || n % 2 == 0
        d = n-1
        d /= 2 while d % 2 == 0
        k.times{
            a = rand(1..n-1)
            t = d
            y = Integer.mod_pow(a, t, n)
            while t != n-1 && y != 1 && y != n-1
                y = y ** 2 % n
                t *= 2
            end
            return false if y != n-1 && t % 2 == 0
        }
        return true
    end
    def self.mod_pow(base, pow, mod)
        result = 1
        while pow > 0
            result = result * base % mod if pow % 2 == 1
            base = base ** 2 % mod
            pow /= 2
        end
        return result
    end
end
h = {
    4 => 3,
    6 => 5,
    8 => 7,
    9 => 7,
    10 => 7,
    12 => 11,
    14 => 13,
    15 => 7,
    16 => 7,
    18 => 8,
    20 => 19,
    21 => 19,
    22 => 7,
    24 => 23,
    25 => 23
}
n = gets.to_i
if h[n]
    puts h[n]
elsif n%8 == 1 && (n-8).miller_rabin_prime?
    puts 14
else
    puts 8
end
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0