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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	小指が強い人
提出日時	2015-12-11 03:33:56
言語	Ruby (3.3.0)
結果	AC
実行時間	83 ms / 1,000 ms
コード長	1,388 bytes
コンパイル時間	176 ms
コンパイル使用メモリ	11,568 KB
実行使用メモリ	15,376 KB
最終ジャッジ日時	2023-08-18 13:24:19
合計ジャッジ時間	12,374 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	80 ms 15,304 KB
testcase_01	AC	80 ms 15,356 KB
testcase_02	AC	77 ms 15,236 KB
testcase_03	AC	78 ms 15,172 KB
testcase_04	AC	78 ms 15,304 KB
testcase_05	AC	79 ms 15,308 KB
testcase_06	AC	78 ms 15,048 KB
testcase_07	AC	80 ms 15,104 KB
testcase_08	AC	78 ms 15,152 KB
testcase_09	AC	79 ms 15,368 KB
testcase_10	AC	77 ms 15,172 KB
testcase_11	AC	78 ms 15,284 KB
testcase_12	AC	78 ms 15,256 KB
testcase_13	AC	77 ms 15,172 KB
testcase_14	AC	79 ms 15,140 KB
testcase_15	AC	79 ms 15,164 KB
testcase_16	AC	79 ms 15,092 KB
testcase_17	AC	78 ms 15,160 KB
testcase_18	AC	78 ms 15,160 KB
testcase_19	AC	78 ms 15,140 KB
testcase_20	AC	77 ms 15,144 KB
testcase_21	AC	77 ms 15,340 KB
testcase_22	AC	77 ms 15,292 KB
testcase_23	AC	78 ms 15,092 KB
testcase_24	AC	79 ms 15,180 KB
testcase_25	AC	78 ms 15,376 KB
testcase_26	AC	79 ms 15,144 KB
testcase_27	AC	79 ms 15,052 KB
testcase_28	AC	78 ms 15,256 KB
testcase_29	AC	77 ms 15,156 KB
testcase_30	AC	78 ms 15,060 KB
testcase_31	AC	78 ms 15,316 KB
testcase_32	AC	77 ms 15,096 KB
testcase_33	AC	80 ms 15,192 KB
testcase_34	AC	79 ms 15,364 KB
testcase_35	AC	79 ms 15,336 KB
testcase_36	AC	79 ms 15,260 KB
testcase_37	AC	78 ms 15,044 KB
testcase_38	AC	78 ms 15,060 KB
testcase_39	AC	79 ms 15,052 KB
testcase_40	AC	80 ms 15,064 KB
testcase_41	AC	78 ms 15,172 KB
testcase_42	AC	79 ms 15,108 KB
testcase_43	AC	78 ms 15,288 KB
testcase_44	AC	79 ms 15,184 KB
testcase_45	AC	83 ms 15,340 KB
testcase_46	AC	78 ms 15,204 KB
testcase_47	AC	78 ms 15,064 KB
testcase_48	AC	78 ms 15,244 KB
testcase_49	AC	78 ms 15,164 KB
testcase_50	AC	81 ms 15,276 KB
testcase_51	AC	78 ms 15,156 KB
testcase_52	AC	78 ms 15,372 KB
testcase_53	AC	78 ms 15,148 KB
testcase_54	AC	78 ms 15,288 KB
testcase_55	AC	79 ms 15,304 KB
testcase_56	AC	79 ms 15,052 KB
testcase_57	AC	79 ms 15,308 KB
testcase_58	AC	78 ms 15,356 KB
testcase_59	AC	77 ms 15,072 KB
testcase_60	AC	78 ms 15,336 KB
testcase_61	AC	77 ms 15,168 KB
testcase_62	AC	78 ms 15,140 KB
testcase_63	AC	78 ms 15,140 KB
testcase_64	AC	78 ms 15,288 KB
testcase_65	AC	79 ms 15,188 KB
testcase_66	AC	78 ms 15,172 KB
testcase_67	AC	78 ms 15,268 KB
testcase_68	AC	78 ms 15,100 KB
testcase_69	AC	77 ms 15,156 KB
testcase_70	AC	77 ms 15,140 KB
testcase_71	AC	78 ms 15,140 KB
testcase_72	AC	78 ms 15,376 KB
testcase_73	AC	80 ms 15,288 KB
testcase_74	AC	79 ms 15,284 KB
testcase_75	AC	78 ms 15,172 KB
testcase_76	AC	77 ms 15,176 KB
testcase_77	AC	78 ms 15,344 KB
testcase_78	AC	78 ms 15,148 KB
testcase_79	AC	78 ms 15,060 KB
testcase_80	AC	79 ms 15,172 KB
testcase_81	AC	80 ms 15,292 KB
testcase_82	AC	79 ms 15,176 KB
testcase_83	AC	79 ms 15,144 KB
testcase_84	AC	81 ms 15,248 KB
testcase_85	AC	78 ms 15,048 KB
testcase_86	AC	80 ms 15,196 KB
testcase_87	AC	80 ms 15,344 KB
testcase_88	AC	78 ms 15,308 KB
testcase_89	AC	78 ms 15,100 KB
testcase_90	AC	80 ms 15,140 KB
testcase_91	AC	77 ms 15,060 KB
testcase_92	AC	80 ms 15,256 KB
testcase_93	AC	78 ms 15,260 KB
testcase_94	AC	78 ms 15,332 KB
testcase_95	AC	82 ms 15,336 KB
testcase_96	AC	78 ms 15,360 KB
testcase_97	AC	78 ms 15,204 KB
testcase_98	AC	78 ms 15,288 KB
testcase_99	AC	77 ms 15,160 KB
testcase_100	AC	78 ms 15,284 KB
testcase_101	AC	81 ms 15,096 KB
testcase_102	AC	79 ms 15,192 KB
testcase_103	AC	77 ms 15,360 KB
testcase_104	AC	79 ms 15,168 KB
testcase_105	AC	78 ms 15,312 KB
testcase_106	AC	78 ms 15,344 KB

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

コンパイルメッセージ

Syntax OK

ソースコード

raw source code

  class Integer
    def prime?
      n = self.abs()
      return true if n == 2
      return false if n == 1 || n & 1 == 0
      d = n-1
      d >>= 1 while d & 1 == 0
      20.times do 
        a = rand(n-2) + 1
        t = d
        y = ModMath.pow(a,t,n)
        while t != n-1 && y != 1 && y != n-1
          y = (y * y) % n
          t <<= 1
        end
        return false if y != n-1 && t & 1 == 0
      end
      return true
    end
  end
  
  module ModMath
    def ModMath.pow(base, power, mod)
      result = 1
      while power > 0
        result = (result * base) % mod if power & 1 == 1
        base = (base * base) % mod
        power >>= 1;
      end
      result
    end
  end
$dx = [1, 0, -1, 0]
$dy = [0, 1, 0, -1]
def find(cx, cy, w)
    t = cy * w + cx
    4.times do |i|
        x = cx + $dx[i]
        y = cy + $dy[i]
        t = y * w + x
        next if x < 0 || x >= w || y < 0 || t + 1 > $n || $b[t]
        return true if t + 1 == $n
        $b[t] = true
        check = find(x, y, w)
        $b[t] = false
        return true if check
    end
    return false
end
$n = gets.to_i
if $n <= 25
    $b = Array.new($n)
    25.times do |j|
        $b[j] = (j + 1).prime?
    end
    25.times do |w|
        w += 1
        if find(0, 0, w)
            puts w
            exit
        end
    end
end
if $n % 8 == 1 && ($n - 8).prime?
    puts 14
else
    puts 8
end

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード