結果
問題 | No.308 素数は通れません |
ユーザー |
|
提出日時 | 2015-12-01 09:21:31 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 102 ms / 1,000 ms |
コード長 | 608 bytes |
コンパイル時間 | 56 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-11-27 18:09:31 |
合計ジャッジ時間 | 11,091 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
コンパイルメッセージ
Syntax OK
ソースコード
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