#61601 (Ruby) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	kura07
提出日時	2015-12-01 02:16:06
言語	Ruby (3.3.0)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	91 ms 12,288 KB
testcase_01	AC	88 ms 12,160 KB
testcase_02	AC	88 ms 12,288 KB
testcase_03	AC	84 ms 12,288 KB
testcase_04	AC	83 ms 12,160 KB
testcase_05	AC	83 ms 12,160 KB
testcase_06	AC	84 ms 12,160 KB
testcase_07	AC	84 ms 12,288 KB
testcase_08	AC	82 ms 12,416 KB
testcase_09	AC	84 ms 12,416 KB
testcase_10	AC	86 ms 12,288 KB
testcase_11	AC	87 ms 12,288 KB
testcase_12	AC	84 ms 12,288 KB
testcase_13	AC	83 ms 12,288 KB
testcase_14	AC	83 ms 12,288 KB
testcase_15	AC	84 ms 12,160 KB
testcase_16	AC	84 ms 12,160 KB
testcase_17	AC	82 ms 12,416 KB
testcase_18	AC	84 ms 12,416 KB
testcase_19	AC	83 ms 12,160 KB
testcase_20	AC	88 ms 12,416 KB
testcase_21	AC	89 ms 12,160 KB
testcase_22	AC	89 ms 12,160 KB
testcase_23	AC	82 ms 12,288 KB
testcase_24	AC	83 ms 12,160 KB
testcase_25	AC	83 ms 12,160 KB
testcase_26	AC	84 ms 12,288 KB
testcase_27	AC	82 ms 12,160 KB
testcase_28	AC	84 ms 12,160 KB
testcase_29	AC	85 ms 12,288 KB
testcase_30	AC	86 ms 12,416 KB
testcase_31	AC	92 ms 12,288 KB
testcase_32	AC	87 ms 12,288 KB
testcase_33	AC	84 ms 12,288 KB
testcase_34	AC	84 ms 12,288 KB
testcase_35	AC	83 ms 12,160 KB
testcase_36	AC	83 ms 12,288 KB
testcase_37	AC	83 ms 12,288 KB
testcase_38	AC	86 ms 12,160 KB
testcase_39	AC	86 ms 12,416 KB
testcase_40	AC	85 ms 12,160 KB
testcase_41	AC	93 ms 12,288 KB
testcase_42	AC	86 ms 12,288 KB
testcase_43	AC	88 ms 12,288 KB
testcase_44	AC	86 ms 12,416 KB
testcase_45	AC	87 ms 12,288 KB
testcase_46	AC	86 ms 12,288 KB
testcase_47	AC	84 ms 12,160 KB
testcase_48	AC	83 ms 12,288 KB
testcase_49	AC	86 ms 12,288 KB
testcase_50	AC	89 ms 12,288 KB
testcase_51	AC	93 ms 12,288 KB
testcase_52	AC	88 ms 12,416 KB
testcase_53	AC	86 ms 12,160 KB
testcase_54	AC	85 ms 12,160 KB
testcase_55	AC	85 ms 12,160 KB
testcase_56	AC	87 ms 12,160 KB
testcase_57	AC	83 ms 12,160 KB
testcase_58	AC	85 ms 12,160 KB
testcase_59	AC	88 ms 12,288 KB
testcase_60	AC	86 ms 12,160 KB
testcase_61	AC	87 ms 12,288 KB
testcase_62	AC	87 ms 12,288 KB
testcase_63	AC	89 ms 12,160 KB
testcase_64	AC	87 ms 12,288 KB
testcase_65	AC	87 ms 12,288 KB
testcase_66	AC	85 ms 12,288 KB
testcase_67	AC	84 ms 12,288 KB
testcase_68	AC	83 ms 12,288 KB
testcase_69	AC	84 ms 12,288 KB
testcase_70	AC	84 ms 12,160 KB
testcase_71	AC	83 ms 12,288 KB
testcase_72	AC	84 ms 12,288 KB
testcase_73	AC	84 ms 12,160 KB
testcase_74	AC	86 ms 12,160 KB
testcase_75	AC	82 ms 12,416 KB
testcase_76	AC	83 ms 12,416 KB
testcase_77	AC	81 ms 12,288 KB
testcase_78	AC	82 ms 12,160 KB
testcase_79	AC	84 ms 12,288 KB
testcase_80	AC	84 ms 12,160 KB
testcase_81	AC	85 ms 12,416 KB
testcase_82	AC	82 ms 12,160 KB
testcase_83	AC	84 ms 12,160 KB
testcase_84	AC	86 ms 12,544 KB
testcase_85	AC	83 ms 12,288 KB
testcase_86	AC	88 ms 12,544 KB
testcase_87	AC	89 ms 12,544 KB
testcase_88	AC	84 ms 12,160 KB
testcase_89	AC	84 ms 12,160 KB
testcase_90	AC	90 ms 12,544 KB
testcase_91	AC	85 ms 12,160 KB
testcase_92	AC	86 ms 12,160 KB
testcase_93	AC	87 ms 12,160 KB
testcase_94	AC	87 ms 12,288 KB
testcase_95	AC	84 ms 12,288 KB
testcase_96	AC	85 ms 12,288 KB
testcase_97	AC	84 ms 12,288 KB
testcase_98	AC	83 ms 12,288 KB
testcase_99	AC	86 ms 12,288 KB
testcase_100	AC	85 ms 12,288 KB
testcase_101	AC	93 ms 12,416 KB
testcase_102	AC	85 ms 12,160 KB
testcase_103	AC	83 ms 12,160 KB
testcase_104	AC	86 ms 12,160 KB
testcase_105	AC	83 ms 12,288 KB
testcase_106	AC	84 ms 12,160 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Syntax OK

ソースコード

raw source code

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード