結果

問題 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
0