結果

問題 No.12 限定された素数
ユーザー tnodino
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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