传统题 1000ms 512MiB

质数情怀

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 K 喜欢玩狼人杀,不过他玩狼人杀和别人有一点不同:小 K 认为质数位的玩家更容易是狼人。

小 K 定义质数位为号码牌为质数的玩家。

现在,小 K 正在玩一个一共有 nn 位玩家参与的狼人杀游戏, nn 位玩家的号码牌从 11nn ,好奇的小 K 对你提出了 qq 个问题,每个问题形如:第 cic_i 大的非质数位的玩家的号码牌是什么。你需要回答小 K 的 qq 个询问。若第 cic_i 大的非质数位的玩家不存在,输出 "-1" (不含引号)。

输入描述

输入第一行两个整数 nn , qq(1n107,1q105)(1 \leq n \leq 10^7,1 \leq q \leq 10^5)

之后 qq 行,每行一个整数 cic_i(1cin)(1 \leq c_i \leq n)

输出格式

对于每个询问,输出一行一个整数,表示答案。若第 cic_i 大的非质数位的玩家不存在,输出 "-1" (不含引号)。

输入输出样例

输入 #1

10 10
1
2
3
4
5
6
7
8
9
10

输出 #1

1
4
6
8
9
10
-1
-1
-1
-1

说明与提示

对于样例 #1:

1101 \sim 10 中,质数有 [2,3,5,7][2,3,5,7] ,非质数有 [1,4,6,8,9,10][1,4,6,8,9,10]

2025暑期集训第六次周赛

未参加
状态
已结束
规则
ACM/ICPC
题目
8
开始于
2025-8-2 14:15
结束于
2025-8-2 18:15
持续时间
4 小时
主持人
参赛人数
62