結果

問題 No.12 限定された素数
ユーザー tnodinotnodino
提出日時 2022-02-02 20:52:57
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 663 ms / 5,000 ms
コード長 1,358 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 87,224 KB
実行使用メモリ 174,368 KB
最終ジャッジ日時 2023-09-02 02:59:28
合計ジャッジ時間 18,097 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 592 ms
173,412 KB
testcase_01 AC 615 ms
173,532 KB
testcase_02 AC 634 ms
173,184 KB
testcase_03 AC 475 ms
173,176 KB
testcase_04 AC 637 ms
173,136 KB
testcase_05 AC 628 ms
174,248 KB
testcase_06 AC 637 ms
173,436 KB
testcase_07 AC 598 ms
173,480 KB
testcase_08 AC 661 ms
173,572 KB
testcase_09 AC 595 ms
173,604 KB
testcase_10 AC 615 ms
173,708 KB
testcase_11 AC 572 ms
173,016 KB
testcase_12 AC 593 ms
173,404 KB
testcase_13 AC 568 ms
173,540 KB
testcase_14 AC 637 ms
173,608 KB
testcase_15 AC 584 ms
173,620 KB
testcase_16 AC 599 ms
174,008 KB
testcase_17 AC 605 ms
173,148 KB
testcase_18 AC 597 ms
172,952 KB
testcase_19 AC 607 ms
173,240 KB
testcase_20 AC 622 ms
173,316 KB
testcase_21 AC 602 ms
173,724 KB
testcase_22 AC 599 ms
173,188 KB
testcase_23 AC 599 ms
173,416 KB
testcase_24 AC 597 ms
173,208 KB
testcase_25 AC 663 ms
174,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

def SieveofEratosthenes(N):
    P = [0] * (N+1)
    P[0] = P[1] = -1
    for i in range(2,N+1):
        if P[i] == 0:
            k = i
            while k <= N:
                P[k] = i
                k += i
            P[i] = 0
    return P

from collections import defaultdict
M = 5000000
P = SieveofEratosthenes(M)
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(10):
    if not i in A:
        B.append(i)
C = []
for i in range(2,M+1):
    if P[i] == 0:
        C.append(i)
M = len(C)
S = [[0] * (10) for _ in range(M+1)]
for i in range(M):
    x = C[i]
    if x == 0 or x == 1 or x == M+1:
        continue
    while x:
        S[i+1][x%10] += 1
        x //= 10
Left = 0
dic = defaultdict(int)
ans = -1
for Right in range(M):
    for i in range(10):
        dic[i] += S[Right][i]
    while Left <= Right:
        flg = True
        for i in B:
            if dic[i]:
                flg = False
        if flg:
            break
        Left += 1
        for i in range(10):
            dic[i] -= S[Left][i]
    flg = True
    for i in A:
        if not dic[i]:
            flg = False
    if flg:
        if C[Left] == 2:
            L = 1
        else:
            L = C[Left-1] + 1
        if C[Right] == 4999999:
            R = 5000000
        else:
            R = C[Right] - 1
        ans = max(ans, R - L)
print(ans)
0