結果
問題 | No.12 限定された素数 |
ユーザー | titia |
提出日時 | 2021-11-02 04:24:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,778 ms / 5,000 ms |
コード長 | 946 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 399,984 KB |
最終ジャッジ日時 | 2024-04-19 09:09:01 |
合計ジャッジ時間 | 57,109 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,927 ms
399,504 KB |
testcase_01 | AC | 2,073 ms
399,812 KB |
testcase_02 | AC | 1,946 ms
399,744 KB |
testcase_03 | AC | 2,778 ms
399,608 KB |
testcase_04 | AC | 1,901 ms
399,384 KB |
testcase_05 | AC | 2,190 ms
399,652 KB |
testcase_06 | AC | 2,137 ms
399,492 KB |
testcase_07 | AC | 2,203 ms
399,516 KB |
testcase_08 | AC | 2,093 ms
399,656 KB |
testcase_09 | AC | 2,021 ms
399,740 KB |
testcase_10 | AC | 2,189 ms
399,984 KB |
testcase_11 | AC | 2,333 ms
399,544 KB |
testcase_12 | AC | 2,209 ms
399,448 KB |
testcase_13 | AC | 2,127 ms
399,728 KB |
testcase_14 | AC | 2,118 ms
399,612 KB |
testcase_15 | AC | 2,062 ms
399,520 KB |
testcase_16 | AC | 2,265 ms
399,512 KB |
testcase_17 | AC | 1,885 ms
399,496 KB |
testcase_18 | AC | 1,845 ms
399,496 KB |
testcase_19 | AC | 1,871 ms
399,648 KB |
testcase_20 | AC | 1,957 ms
399,484 KB |
testcase_21 | AC | 2,029 ms
399,508 KB |
testcase_22 | AC | 1,903 ms
399,516 KB |
testcase_23 | AC | 1,924 ms
399,492 KB |
testcase_24 | AC | 1,931 ms
399,528 KB |
testcase_25 | AC | 2,182 ms
399,640 KB |
ソースコード
from collections import Counter N=int(input()) A=Counter(input().split()) x=5000000 import math L=math.floor(math.sqrt(x)) # 平方根を求める Primelist=[i for i in range(x+1)] Primelist[1]=0 # 1は素数でないので0にする. for i in Primelist: if i>L: break if i==0: continue for j in range(2*i,x+1,i): Primelist[j]=0 Primes=[0]+[Primelist[j] for j in range(x+1) if Primelist[j]!=0] P2=[] for p in Primes: P2.append(Counter(str(p))) S=Counter() ANS=-1 end=1 for now in range(1,len(Primes)): while set(S)<=set(A): if set(S)==set(A): if end==348514: ANS=max(ANS,5000001-Primes[now-1]-2) else: ANS=max(ANS,Primes[end]-Primes[now-1]-2) if end==348514: break S+=P2[end] end+=1 #print(Primes[now],Primes[end],ANS,A,S) S-=P2[now] print(ANS)