首页 > 试题广场 >

小红的“质数”寻找

[编程题]小红的“质数”寻找
  • 热度指数：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 的数位之和为 1，2 的数位之和为 2，1 既不属于合数、也不是质数；所以 2 是唯一答案。
\hspace{15pt}对于第二组测试数据，14 的数位之和为 1+4=5，符合条件。注意答案不唯一。
算法知识视频讲解
添加回答
Java
在思考的大白菜很深情头像 在思考的大白菜很深情
import java.util.Scanner;

public class Main {
    static int[] table = {-1, 2, 3, 5, 5, 7, 7, 11, 11, 11};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取组数
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            sc.nextLine(); // 吃掉换行符

            for (int i = 0; i < n; i++) {
                String s = sc.nextLine().trim();

                if (s.length() > 0 && Character.isDigit(s.charAt(0))) {
                    int firstDigit = s.charAt(0) - '0';
                    int firstPrime = table[firstDigit];

                    // 构造：firstPrime + 若干个0
                    StringBuilder sb = new StringBuilder();
                    sb.append(firstPrime);
                    for (int j = 1; j < s.length(); j++) {
                        sb.append('0');
                    }

                    System.out.println(sb.toString());
                }
            }
        }
    }
}

发表于 2025-07-27 09:55:45 回复(0)
提交观点

问题信息

数论
难度：
2条回答 413浏览

热门推荐

相关试题

小红的“质数”寻找

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号