結果
問題 |
No.12 限定された素数
|
ユーザー |
![]() |
提出日時 | 2020-03-19 14:06:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 288 ms / 5,000 ms |
コード長 | 1,057 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 137,868 KB |
最終ジャッジ日時 | 2024-11-24 10:25:53 |
合計ジャッジ時間 | 8,483 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#!/usr/bin/ python3.8 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N = int(readline()) A = map(int, read().split()) full = 0 for x in A: full += (1 << x) def num_to_set(n): x = 0 while n: n, r = divmod(n, 10) x |= (1 << r) return x U = 5 * 10 ** 6 + 1 is_prime = [0] * U is_prime[2] = 1 for n in range(3, U, 2): is_prime[n] = 1 for p in range(3, U, 2): if p * p >= U: break if is_prime[p]: for i in range(p * p, U, p + p): is_prime[i] = 0 ng = [] ok = [] for p in range(U): if is_prime[p]: s = num_to_set(p) if s & (~full): ng.append(p) else: ok.append((p, s)) ng.append(U) ok.append((U, 0)) L = 1 i = 0 answer = -1 for x in ng: R = x - 1 se = 0 while True: p, s = ok[i] if p > R: break se |= s i += 1 if se == full and answer < R - L: answer = R - L L = x + 1 print(answer)