結果

問題 No.308 素数は通れません
ユーザー cympfh
提出日時 2015-12-01 09:21:31
言語 Ruby
(2.4.1)
結果
AC  
実行時間 22 ms
コード長 608 Byte
コンパイル時間 20 ms
使用メモリ 4156 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_small_00.txt AC 10 ms
4076 KB
0_small_01.txt AC 12 ms
4072 KB
0_small_02.txt AC 9 ms
4068 KB
0_small_03.txt AC 9 ms
4072 KB
0_small_04.txt AC 9 ms
4076 KB
0_small_05.txt AC 10 ms
4080 KB
0_small_06.txt AC 10 ms
4072 KB
0_small_07.txt AC 10 ms
4080 KB
0_small_08.txt AC 9 ms
4076 KB
0_small_09.txt AC 9 ms
4068 KB
0_small_10.txt AC 10 ms
4076 KB
0_small_11.txt AC 9 ms
4084 KB
0_small_12.txt AC 9 ms
4076 KB
0_small_13.txt AC 9 ms
4072 KB
0_small_14.txt AC 8 ms
4084 KB
0_small_15.txt AC 9 ms
4068 KB
0_small_16.txt AC 9 ms
4084 KB
0_small_17.txt AC 9 ms
4076 KB
0_small_18.txt AC 9 ms
4072 KB
0_small_19.txt AC 8 ms
4072 KB
0_small_20.txt AC 9 ms
4096 KB
0_small_21.txt AC 8 ms
4068 KB
0_small_22.txt AC 9 ms
4072 KB
0_small_23.txt AC 22 ms
4072 KB
0_small_24.txt AC 9 ms
4076 KB
0_small_25.txt AC 9 ms
4072 KB
0_small_26.txt AC 9 ms
4072 KB
0_small_27.txt AC 9 ms
4076 KB
0_small_28.txt AC 9 ms
4072 KB
0_small_29.txt AC 9 ms
4076 KB
0_small_30.txt AC 8 ms
4068 KB
0_small_31.txt AC 9 ms
4072 KB
0_small_32.txt AC 9 ms
4100 KB
0_small_33.txt AC 9 ms
4072 KB
0_small_34.txt AC 9 ms
4084 KB
0_small_35.txt AC 8 ms
4072 KB
1_middle_00.txt AC 9 ms
4072 KB
1_middle_01.txt AC 9 ms
4072 KB
1_middle_02.txt AC 10 ms
4076 KB
1_middle_03.txt AC 9 ms
4072 KB
1_middle_04.txt AC 9 ms
4072 KB
1_middle_05.txt AC 9 ms
4072 KB
1_middle_06.txt AC 10 ms
4080 KB
1_middle_07.txt AC 9 ms
4080 KB
1_middle_08.txt AC 8 ms
4084 KB
1_middle_09.txt AC 9 ms
4068 KB
1_middle_10.txt AC 9 ms
4068 KB
1_middle_11.txt AC 9 ms
4076 KB
1_middle_12.txt AC 9 ms
4080 KB
1_middle_13.txt AC 9 ms
4072 KB
1_middle_14.txt AC 8 ms
4080 KB
1_middle_15.txt AC 8 ms
4080 KB
1_middle_16.txt AC 9 ms
4080 KB
1_middle_17.txt AC 9 ms
4080 KB
1_middle_18.txt AC 8 ms
4068 KB
1_middle_19.txt AC 9 ms
4076 KB
2_large_00.txt AC 9 ms
4100 KB
2_large_01.txt AC 9 ms
4076 KB
2_large_02.txt AC 9 ms
4072 KB
2_large_03.txt AC 9 ms
4072 KB
2_large_04.txt AC 8 ms
4076 KB
2_large_05.txt AC 9 ms
4072 KB
2_large_06.txt AC 8 ms
4068 KB
2_large_07.txt AC 9 ms
4124 KB
2_large_08.txt AC 8 ms
4076 KB
2_large_09.txt AC 9 ms
4072 KB
2_large_10.txt AC 9 ms
4076 KB
2_large_11.txt AC 9 ms
4072 KB
2_large_12.txt AC 9 ms
4084 KB
2_large_13.txt AC 8 ms
4084 KB
2_large_14.txt AC 9 ms
4088 KB
2_large_15.txt AC 12 ms
4092 KB
2_large_16.txt AC 8 ms
4088 KB
2_large_17.txt AC 8 ms
4084 KB
2_large_18.txt AC 9 ms
4096 KB
2_large_19.txt AC 9 ms
4092 KB
3_strong_00.txt AC 9 ms
4096 KB
3_strong_01.txt AC 9 ms
4080 KB
3_strong_02.txt AC 9 ms
4072 KB
3_strong_03.txt AC 9 ms
4080 KB
3_strong_04.txt AC 9 ms
4100 KB
3_strong_05.txt AC 11 ms
4128 KB
3_strong_06.txt AC 9 ms
4076 KB
3_strong_07.txt AC 9 ms
4076 KB
3_strong_08.txt AC 13 ms
4128 KB
3_strong_09.txt AC 9 ms
4072 KB
3_strong_10.txt AC 13 ms
4128 KB
3_strong_11.txt AC 13 ms
4124 KB
3_strong_12.txt AC 8 ms
4072 KB
3_strong_13.txt AC 9 ms
4076 KB
3_strong_14.txt AC 14 ms
4156 KB
3_strong_15.txt AC 9 ms
4084 KB
3_strong_16.txt AC 9 ms
4084 KB
3_strong_17.txt AC 9 ms
4084 KB
3_strong_18.txt AC 9 ms
4092 KB
3_strong_19.txt AC 9 ms
4092 KB
4_hand_01.txt AC 9 ms
4120 KB
challenge01.txt AC 9 ms
4144 KB
challenge02.txt AC 9 ms
4140 KB
system_test1.txt AC 14 ms
4156 KB
system_test2.txt AC 9 ms
4084 KB
system_test3.txt AC 8 ms
4084 KB
system_test4.txt AC 9 ms
4088 KB
system_test5.txt AC 8 ms
4080 KB
system_test6.txt AC 9 ms
4148 KB
テストケース一括ダウンロード

ソースコード

diff #
m={4=>3,6=>5,8=>7,9=>7,10=>7,15=>7,16=>7,22=>7,12=>11,14=>13,20=>19,21=>19,24=>23,25=>23}

def powmod(a,k,m)
  return 1 if k == 0
  t = powmod(a, k / 2, m)
  t = t * t % m
  t = t * a % m if k.odd?
  return t
end

def prime?(n)
  return false if n<2
  return true if n<4
  return false if n.even?
  d = n-1
  d >>= 1 while d.even?
  100.times do
    a = rand(n-1) + 1
    y = powmod(a, d, n)
    t = d
    while t != n-1 and y != 1 and y != n-1
      y = (y*y) % n
      t <<= 1
    end
    return false if y!=n-1 and t.even?
  end
  return true
end

n=gets.chomp.to_i
p m[n]?m[n]:(n%8==1&&prime?(n-8))?14:8
0