結果
問題 | No.12 限定された素数 |
ユーザー | titia |
提出日時 | 2021-11-02 04:24:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,739 ms / 5,000 ms |
コード長 | 946 bytes |
コンパイル時間 | 519 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 400,336 KB |
最終ジャッジ日時 | 2024-10-11 01:42:26 |
合計ジャッジ時間 | 57,984 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,909 ms
399,408 KB |
testcase_01 | AC | 2,112 ms
399,396 KB |
testcase_02 | AC | 1,873 ms
400,336 KB |
testcase_03 | AC | 2,739 ms
399,448 KB |
testcase_04 | AC | 1,933 ms
399,284 KB |
testcase_05 | AC | 2,223 ms
399,692 KB |
testcase_06 | AC | 2,151 ms
399,384 KB |
testcase_07 | AC | 2,165 ms
399,576 KB |
testcase_08 | AC | 2,131 ms
399,896 KB |
testcase_09 | AC | 2,065 ms
399,412 KB |
testcase_10 | AC | 2,158 ms
399,760 KB |
testcase_11 | AC | 2,297 ms
399,480 KB |
testcase_12 | AC | 2,262 ms
399,620 KB |
testcase_13 | AC | 2,123 ms
399,592 KB |
testcase_14 | AC | 2,083 ms
399,556 KB |
testcase_15 | AC | 2,120 ms
399,456 KB |
testcase_16 | AC | 2,218 ms
399,520 KB |
testcase_17 | AC | 1,911 ms
399,236 KB |
testcase_18 | AC | 1,867 ms
399,384 KB |
testcase_19 | AC | 1,943 ms
399,740 KB |
testcase_20 | AC | 1,981 ms
399,464 KB |
testcase_21 | AC | 2,036 ms
399,436 KB |
testcase_22 | AC | 1,908 ms
399,632 KB |
testcase_23 | AC | 1,883 ms
399,364 KB |
testcase_24 | AC | 1,889 ms
399,512 KB |
testcase_25 | AC | 2,168 ms
399,720 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)