結果
問題 | No.308 素数は通れません |
ユーザー |
|
提出日時 | 2015-12-01 20:42:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 80 ms / 1,000 ms |
コード長 | 1,353 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-11-27 18:17:44 |
合計ジャッジ時間 | 6,025 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
外部呼び出し有り |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
#!/usr/bin/env python3 def is_prime(n): if n**0.5 < 10**5: if n == 1: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True else: import subprocess factors = list(map(int,subprocess.check_output(['factor', str(n)]).split()[1:])) return len(factors) == 1 def bfs(n, w, initial, accept, deny=None): que = [initial] i = 0 pushed = set(que) while i < len(que): if accept(que, i): return True if deny is not None and deny(que, i): return False x = que[i] i += 1 def f(y): if y not in pushed and not is_prime(y): que.append(y) pushed.add(y) if x-1 > 0 and x % w != 1: f(x-1) if x+1 <= n and x % w != 0: f(x+1) if x-w > 0: f(x-w) if x+w <= n: f(x+w) def solve(n): if n < 300: # magic number for w in range(1,n): if bfs(n, w, 1, lambda que, i: que[i] == n): return w else: for w in range(2,n): if bfs(n, w, 1, lambda que, i: que[i] % w == 0) \ and bfs(n, w, n, lambda que, i: len(que) >= 10): # magic number return w print(solve(int(input())))