結果

問題 No.12 限定された素数
ユーザー tnodinotnodino
提出日時 2022-02-02 20:52:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 628 ms / 5,000 ms
コード長 1,358 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 172,940 KB
最終ジャッジ日時 2024-06-11 09:36:20
合計ジャッジ時間 16,766 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 571 ms
171,648 KB
testcase_01 AC 611 ms
171,912 KB
testcase_02 AC 608 ms
171,516 KB
testcase_03 AC 455 ms
171,400 KB
testcase_04 AC 628 ms
171,664 KB
testcase_05 AC 586 ms
172,684 KB
testcase_06 AC 567 ms
171,908 KB
testcase_07 AC 565 ms
171,640 KB
testcase_08 AC 615 ms
172,936 KB
testcase_09 AC 566 ms
171,776 KB
testcase_10 AC 586 ms
172,040 KB
testcase_11 AC 547 ms
171,772 KB
testcase_12 AC 579 ms
171,720 KB
testcase_13 AC 562 ms
171,788 KB
testcase_14 AC 599 ms
172,676 KB
testcase_15 AC 554 ms
172,032 KB
testcase_16 AC 570 ms
172,940 KB
testcase_17 AC 565 ms
171,688 KB
testcase_18 AC 561 ms
171,512 KB
testcase_19 AC 568 ms
171,784 KB
testcase_20 AC 580 ms
171,904 KB
testcase_21 AC 586 ms
172,168 KB
testcase_22 AC 564 ms
171,648 KB
testcase_23 AC 564 ms
171,660 KB
testcase_24 AC 571 ms
171,652 KB
testcase_25 AC 587 ms
172,676 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