結果
問題 |
No.308 素数は通れません
|
ユーザー |
![]() |
提出日時 | 2015-12-01 21:23:39 |
言語 | Python2 (2.7.18) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,264 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-09-14 06:25:52 |
合計ジャッジ時間 | 6,319 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 106 WA * 1 |
ソースコード
from random import randint from collections import deque from math import sqrt n = input() M = min(10003, n) prime = [1]*(M+1) prime[0] = prime[1] = 0 p_num = 0 for i in xrange(2, int(sqrt(M))+1): if prime[i]: for j in xrange(i*i, M+1, i): prime[j] = 0 def fermat(k): for t in xrange(10000): a = randint(2, k-1) if pow(a, k-1, k)!=1: return 0 return 1 i = 2 while i<=40: deq = deque() deq.append(1) used = [0]*(M+1) ok = 0 while deq: v = deq.popleft() if n>M and v%i==0: ok = 1 break if v==n: print i exit(0) if v+1 <= M and v%i!=0 and not prime[v+1] and not used[v+1]: used[v+1] = 1 deq.append(v+1) if v-1 >= 1 and v%i!=1 and not prime[v-1] and not used[v-1]: used[v-1] = 1 deq.append(v-1) if v+i <= M and not prime[v+i] and not used[v+i]: used[v+i] = 1 deq.append(v+i) if v-i >= 1 and not prime[v-i] and not used[v-i]: used[v-i] = 1 deq.append(v-i) if ok: if (n%i!=1 and not fermat(n-1)) or not fermat(n-i): print i exit(0) i += 1 exit(1)