結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 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
ソースコード
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