小红的“质数”寻找

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

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

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

输入描述:

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

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

输出描述:

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

示例1

输入

2
1
11

输出

2
14

说明

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

算法知识视频讲解

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)