首页 > 试题广场 >

小红的“质数”寻找

[编程题]小红的“质数”寻找
  • 热度指数:2373 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 1024M,其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}小红拿到了一个正整数 x,她希望你在 [x, 2 \times x] 区间内找到一个正整数,满足该正整数所有数位之和为一个质数,你能帮帮她吗?

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^5\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}在一行上输入一个正整数 x \left(1\leqq x\leqq 10^{100\,000}\right)

\hspace{15pt}除此之外,保证单个测试文件的 x 之和小于 10^{1\,000\,000}


输出描述:
\hspace{15pt}对于每一组测试数据,新起一行。如果不存在满足条件的正整数,直接输出 -1;否则,输出一个正整数,代表答案。
\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

2
1
11

输出

2
14

说明

\hspace{15pt}对于第一组测试数据,我们需要在 [1,2] 区间内找到一个正整数,满足该正整数所有数位之和为一个质数。其中,1 的数位之和为 12 的数位之和为 21 既不属于合数、也不是质数;所以 2 是唯一答案。
\hspace{15pt}对于第二组测试数据,14 的数位之和为 1+4=5,符合条件。注意答案不唯一。

这道题你会答吗?花几分钟告诉大家答案吧!