結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2015-12-01 23:24:27 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 43 ms / 1,000 ms |
コード長 | 643 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 7,076 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-11-27 18:24:52 |
合計ジャッジ時間 | 4,445 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
from random import randint n = input() m = {3: [4], 5: [6], 7: [8,9,10,15,16,22], 11: [12], 13: [14], 19: [20,21], 23: [24,25]} def miller_rabin(n): if n==2: return 1 if n==1 or n&1==0: return 0 d = n-1 d /= d & -d for k in xrange(1000): a = randint(1, n-1) t = d y = pow(a, t, n) while t!=n-1 and y!=1 and y!=n-1: y = y**2 % n t <<= 1 if y!=n-1 and t&1==0: return 0 return 1 for w in m: if n in m[w]: print w break else: if (n%8!=1 and not miller_rabin(n-1)) or not miller_rabin(n-8): print 8 else: print 14