我要招人

去企业版

首页 > 试题广场 >

小红的“质数”寻找

[编程题]小红的“质数”寻找

热度指数：2361 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 小红拿到了一个正整数 $x$ ，她希望你在 $[x, 2 \times x]$ 区间内找到一个正整数，满足该正整数所有数位之和为一个质数，你能帮帮她吗？

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入一个正整数 。

除此之外，保证单个测试文件的  之和小于 。

输出描述:

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

示例1

输入

2
1
11

输出

2
14

说明

对于第一组测试数据，我们需要在  区间内找到一个正整数，满足该正整数所有数位之和为一个质数。其中， 的数位之和为 ， 的数位之和为 ， 既不属于合数、也不是质数；所以  是唯一答案。
对于第二组测试数据， 的数位之和为 ，符合条件。注意答案不唯一。

算法知识视频讲解

C++

黑榜o小兔

题目描述是找到 [x, 2x] 范围内满足所有数位和为质数，X数据大到10w位，直接查肯定不行

需要转换一下思路，因为要求只要1个结果，自己构造肯定是怎么方便怎么来

所以只需要考虑答案的前1~2位，后面全部补0，这样就是最简单的办法

现在来确定一下范围就行，

当X = 1.ddd × 10ⁿ ，[ x, 2x] 范围就是 [1.ddd × 10ⁿ , 2(or3).ddd × 10ⁿ]，那么2 × 10ⁿ肯定是在这个范围内的

以此类推，X = 2.ddd × 10ⁿ 时，3 × 10ⁿ 在目标范围内...这样一直推到9就好

有了这样的结论就可以下手了

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<int> table = {-1, 2, 3, 5, 5, 7, 7, 11, 11, 11};

int main() {
    int cnt;
    while (cin >> cnt) { 
        string s;
        while(cnt-- > 0){
            cin >> s;
            int len = s.size();
            cout << table[s[0] - '0'] <<  string(len - 1, '0') << endl;
        }
    }
}

发表于 2025-04-30 15:16:27 回复(2)

惊羽_

输入11，范围11~22，11的数位和是2也满足条件啊，为啥我做的就不行？

def sm(n):

return sum(int(c) for c in str(n))

def isprime(n):

if n < 2:

return False

if n == 2:

return True

for i in range(3, int(n**0.5)+1, 2):

if n % i == 0:

return False

else:

return True

while True:

try:

T = int(input())

for _ in range(T):

x = int(input())

l = []

for i in range(x,2*x+1):

if isprime(sm(i)):

l.append(i)

if len(l) > 0:

print(l[0])

else:

print(-1)

except:

break

发表于 2025-03-23 20:50:32 回复(1)

张吉群

第一个测试用例目测是100位数，题目上写的最大10^6,服了

发表于 2025-04-02 11:32:11 回复(0)

Python 3

菜鸟小乔

T = int(input())

# 自己构造质数
        
for _ in range(T):
    x = input()
    k = len(x)
    if x[0]=='1':
        result = '2'+ '0'*(k-1)
    elif x[0]=='2':
        result = '3' + '0'*(k-1)
    elif x[0]=='3':
        result = '5' + '0'*(k-1)
    elif x[0]=='4':
        result = '7' + '0'*(k-1)
    elif x[0]=='5':
        result = '7' + '0'*(k-1)
    elif x[0]=='6':
        result = '7' + '0'*(k-1)
    elif x[0]=='7':
        result = '11' + '0'*(k-1)
    elif x[0]=='8':
        result = '11' + '0'*(k-1)
    elif x[0]=='9':
        result = '11' + '0'*(k-1)
    print(result)

发表于 2025-08-03 13:12:36 回复(0)

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)

pypy3

一个毕业生a

import math
def is_sushu(a):
    if a ==1:
        return False
    if a ==2:
        return True
    up_jie = math.sqrt(a)
    i = 2
    while i <= up_jie:
        if a % i == 0:
            return False
        i += 1
    return True
n = int(input())

for i in range(n):
    k = int(input())
    for t in range(k,2*k+1):
        sum_wei = 0
        temp = list(str(t))
        for char in temp:
            sum_wei += int(char)
        if is_sushu(sum_wei):
            print(t)
            break
#一个例子超时了，草

发表于 2025-04-10 20:50:34 回复(0)

C++

瑞克1

败给你们这些数学家了。。心服口服。。。

发表于 2025-03-22 02:38:30 回复(0)

提交观点

问题信息

数论

难度：

7条回答 28收藏 407浏览

小红的“质数”寻找

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题