Python3 解法, 执行用时: 3039ms, 内存消耗: 118416K, 提交时间: 2023-03-10 17:11:19

MAX=3456789
arr=[0]*MAX
prime=[0]*MAX
b=[0]*MAX
k=0
g=0
for i in range(2,MAX,1):
    if 0==arr[i]:
        for j in range(i**2,MAX,i): arr[j]=1
for i in range(2,MAX):
    if 0==arr[i]:
        prime[k]=i
        k+=1
n,t=map(int,input().split(" "))
a=list(map(int,input().split(" ")))
for i in range(n):
    if a[i]<MAX: arr[a[i]]=1
    while arr[prime[g]]==1: g+=1
    b[i]=prime[g]
for i in range(t):
    e=int(input())-1
    print(b[e])

pypy3 解法, 执行用时: 3018ms, 内存消耗: 121684K, 提交时间: 2022-09-21 15:17:19

n,q=map(int,input().split(' '))
a=list(map(int,input().split(' ')))
arr=[0]*(5*10**6)
brr=[]
for i in range(2,5*10**6):
    for j in range(i,5*10**6,i):
        if arr[i]==0:
            brr.append(i)
            arr[i]=1
        arr[j]=1
dp=[] #记录前i个的最小质数
seen=set()
k=0
for item in a:
    seen.add(item)
    while brr[k] in seen:
        k+=1
    dp.append(brr[k])

for i in range(q):
    x=int(input())
    print(dp[x-1])

C++(g++ 7.5.0) 解法, 执行用时: 684ms, 内存消耗: 12432K, 提交时间: 2022-08-26 21:33:33

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+100;
int a,c[N];
bool b[N];
int main() {
	int n,q,x,t=2;
	cin>>n>>q;
	for(int i=2; i<=N-100; i++) {
		if(!b[i]) {
			for(int j=i*2; j<=N-100; j+=i)
				b[j]=1;
		}
	}
	for(int i=1; i<=n; i++) {
		cin>>a;
		if(a<=N-100) b[a]=1;
		while(b[t]) t++;
		c[i]=t;
	}
	while(q--) {
		cin>>x;
		cout<<c[x]<<endl;
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 709ms, 内存消耗: 13236K, 提交时间: 2022-08-27 16:42:43

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+100;
int a,c[N];
bool b[N];
int main() {
	int n,q,x,t=2;
	cin>>n>>q;
	for(int i=2; i<=N-100; i++) {
		if(!b[i]) {
			for(int j=i*2; j<=N-100; j+=i)
				b[j]=1;
		}
	}
	for(int i=1; i<=n; i++) {
		cin>>a;
		if(a<=N) b[a]=1;
		while(b[t]) t++;
		c[i]=t;
	}
	while(q--) {
		cin>>x;
		cout<<c[x]<<endl;
	}
	return 0;
}