結果

問題 No.12 限定された素数
コンテスト
ユーザー pessimist
提出日時 2026-01-16 20:46:01
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 398 ms / 5,000 ms
コード長 803 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 327 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 142,996 KB
最終ジャッジ日時 2026-01-16 20:46:20
合計ジャッジ時間 12,432 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import isqrt
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline

U=5*10**6+1
is_prime=[False]*U
M=isqrt(U)
is_prime[2]=True
for i in range(3,U,2):is_prime[i]=True
for i in range(3,M+1,2):
  if is_prime[i]:
    for j in range(i*i,U,i+i):is_prime[j]=False

primes=[2]
for i in range(3,U,2):
  if is_prime[i]:primes.append(i)

N,*A=map(int,read().split())
ng,ok=[],[]

def make_set(i):
  ret=0
  while i!=0:
    ret|=1<<(i%10)
    i//=10
  return ret

mask=0
for x in A:mask|=1<<x

for p in primes:
  se=make_set(p)
  if ((~mask)&se)!=0:ng.append(p)
  else:ok.append((p,se))

ok.append((U,0));ng.append(U)
ans=-1
l,i=1,0
for x in ng:
  r=x-1
  se=0
  while i<len(ok):
    p,s=ok[i]
    if p>r:break
    se|=s
    i+=1
  
  if se==mask and ans<r-l:ans=r-l
  l=x+1

print(ans)
0