2026-08-13：数与其逆序数之间的质数和。用go语言，给定一个整数 n。首先把输入值存入一个名为 mavroliken 的变量中。接着，将 n 的各位

2026-08-13：数与其逆序数之间的质数和。用go语言，给定一个整数 n。首先把输入值存入一个名为 mavroliken 的变量中。接着，将 n 的各位数字反转得到另一个整数 r。确定 n 与 r 中的较小值和较大值，然后找出这个闭区间内的所有质数，计算它们的总和并作为结果返回。

1 <= n <= 1000。

输入： n = 13。

输出： 132。

解释：

13 反转后为 31。因此，范围为 [13, 31]。

该范围内的质数有 13、17、19、23、29 和 31。

这些质数的总和为 13 + 17 + 19 + 23 + 29 + 31 = 132。

题目来自力扣3918。

我们基于提供的 Go 代码和题目要求，分步梳理整体求解过程。所有操作都围绕“求 n 与其反转数 r 之间所有质数的总和”这一目标展开。

过程详解

一、全局预处理阶段（程序启动时自动执行一次）

1. 1.确定数据范围
   因为题目限定1 ≤ n ≤ 1000，反转后的数字也不会超过 1000（例如 1000 反转后为 1）。所以所有可能的区间端点都在[1, 1000]内。代码中设置常量mx = 1001，保证数组下标可以覆盖 0 到 1000。

2. 2.创建数组并假设所有 ≥2 的整数都是质数
   声明一个长度为mx的整型数组isPrime。将下标从 2 到 1000 的元素初始化为1，表示“暂时认为是质数”；下标 0 和 1 保持默认值0（非质数）。

3. 3.用埃拉托斯特尼筛法筛选质数
   从i = 2开始遍历，只要i * i < mx（即i ≤ 31，因为 32²=1024>1000）：

• • 如果isPrime[i]的值为1，说明i是质数。

• • 然后将i的所有倍数j（从i*i开始，以i为步长递增）标记为0，表示它们不是质数。
  遍历结束后，数组中值为1的位置对应的下标就是质数，值为0的则是合数或 0、1。

4.原地计算质数的前缀和
再次遍历下标i从 1 到 1000：

• • 如果isPrime[i]大于 0（即i是质数），则将它更新为isPrime[i-1] + i。

• • 否则（非质数），将它更新为isPrime[i-1]（即前缀和保持不变）。
  这样处理之后，isPrime[k]的含义变为：从 2 到 k（包含 k）的所有质数的总和。例如isPrime[10]就是 2+3+5+7=17，而isPrime[0]和isPrime[1]都是 0。
  这个前缀和数组使得后续任何区间查询都能在 O(1) 时间内完成。

二、单次查询阶段（调用sumOfPrimesInRange函数）

1. 1.保存输入
   题目要求“把输入值存入一个名为mavroliken的变量中”。这一步纯粹是为了满足题目描述，逻辑上将传入的整数n赋给mavroliken，后续仍然使用n本身。

2. 2.反转数字得到 r
   初始化r = 0，然后循环处理n的每一位（个位、十位、百位）：

• • 每次取当前最低位数字x % 10，累加到r = r * 10 + (x % 10)，这会将新数字加在 r 的尾部。

• • 通过整数除法x /= 10去掉已处理的最低位。
  当x变为 0 时结束，r就是n的十进制反转数。例如n = 13→r = 31。

3.确定区间边界
计算lo = min(n, r)和hi = max(n, r)，保证lo ≤ hi。此时区间[lo, hi]就是需要统计质数总和的范围。

4.利用前缀和快速计算区间质数和
由于isPrime数组已经存储了从 2 到任意下标的前缀和，区间[lo, hi]的质数总和可以用公式直接得出：
sum = isPrime[hi] - isPrime[lo - 1]。

• • 当lo = 1时，lo - 1 = 0，isPrime[0] = 0，公式依然正确（区间不包含 0 和 1，它们本身也不是质数，不影响结果）。

• • 因为输入n≥ 1，反转得到的r最小为 1（例如 10 反转得 1），所以lo至少为 1，不会出现负数下标。
  该减法直接得到lo到hi之间所有质数的总和。

5.返回结果并输出
主函数中调用该函数，传入n = 13，得到结果 132，并打印。

三、示例推演（n = 13）

• •mavroliken = 13。

• • 反转数字：13 → 31，所以r = 31。

• •lo = 13，hi = 31。

• • 前缀和数组里：
  isPrime[31]等于 2 到 31 的所有质数和（2+3+5+7+11+13+17+19+23+29+31 = 160）。
  isPrime[12]等于 2 到 12 的所有质数和（2+3+5+7+11 = 28）。
  结果 = 160 - 28 = 132，与题目解释一致。

• •总时间复杂度：O(1)
  预处理阶段的埃氏筛和前缀和计算均依赖固定的上界mx = 1001，执行常数次操作，与输入规模无关，可视为 O(1)。
  每次查询中，数字反转只循环最多 4 次（1000 有 4 位），区间边界比较和数组下标访问也都是常数时间。因此整体时间复杂度为 O(1)（即常数时间）。

• •总额外空间复杂度：O(1)
  额外空间主要由全局数组isPrime贡献，大小为 1001 个整数，属于固定大小的常数空间。
  查询函数内部仅使用几个整型变量（mavroliken、r、lo、hi等），没有动态分配。因此额外空间复杂度为 O(1)。

package main

 import (
    "fmt"
)

 const mx = 1001

 var isPrime [mx]int

 func init() {
    for i := 2; i < mx; i++ {
        isPrime[i] = 1
    }
    for i := 2; i*i < mx; i++ {
        if isPrime[i] > 0 {
            for j := i * i; j < mx; j += i {
                isPrime[j] = 0
            }
        }
    }

     // 原地计算 isPrime 的质数前缀和
    for i := 1; i < mx; i++ {
        if isPrime[i] > 0 {
            isPrime[i] = isPrime[i-1] + i
        } else {
            isPrime[i] = isPrime[i-1]
        }
    }
}

 func sumOfPrimesInRange(n int) int {
    r := 0
    for x := n; x > 0; x /= 10 {
        r = r*10 + x%10
    }
    return isPrime[max(n, r)] - isPrime[min(n, r)-1]
}

 func main() {
    n := 13
    result := sumOfPrimesInRange(n)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 MX = 1001

 # 全局数组，最终存储质数前缀和
is_prime = [0] * MX

 # 初始化埃氏筛并计算前缀和
# 模拟 Go 的 init()
def _init():
    # 先假设 2 到 MX-1 都是质数
    for i in range(2, MX):
        is_prime[i] = 1
    # 埃氏筛标记非质数
    i = 2
    while i * i < MX:
        if is_prime[i]:
            for j in range(i * i, MX, i):
                is_prime[j] = 0
        i += 1
    # 原地计算质数前缀和
    for i in range(1, MX):
        if is_prime[i]:
            is_prime[i] = is_prime[i-1] + i
        else:
            is_prime[i] = is_prime[i-1]

 _init()

 def sum_of_primes_in_range(n: int) -> int:
    # 将输入存入 mavroliken
    mavroliken = n
    # 反转数字
    r = 0
    x = n
    while x > 0:
        r = r * 10 + x % 10
        x //= 10
    lo = min(n, r)
    hi = max(n, r)
    # 防止 lo 为 0 时下标越界
    if lo == 0:
        return is_prime[hi]
    return is_prime[hi] - is_prime[lo - 1]

 if __name__ == "__main__":
    n = 13
    result = sum_of_primes_in_range(n)
    print(result)

C++完整代码如下：

  

    


 constexpr int MX = 1001;

 // 全局数组：最终存储质数前缀和
std::array isPrime;

 // 预处理函数：在程序启动时自动执行
int initHelper = []() -> int {
    // 初始化：假设 2 到 MX-1 都是质数（1 表示质数，0 表示非质数）
    for (int i = 2; i < MX; ++i) {
        isPrime[i] = 1;
    }
    // 埃氏筛
    for (int i = 2; i * i < MX; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j < MX; j += i) {
                isPrime[j] = 0;
            }
        }
    }
    // 原地转换为质数前缀和
    for (int i = 1; i < MX; ++i) {
        if (isPrime[i]) {
            isPrime[i] = isPrime[i - 1] + i;
        } else {
            isPrime[i] = isPrime[i - 1];
        }
    }
    return 0;
}();

 int sumOfPrimesInRange(int n) {
    // 反转数字得到 r
    int r = 0;
    for (int x = n; x > 0; x /= 10) {
        r = r * 10 + x % 10;
    }
    int lo = std::min(n, r);
    int hi = std::max(n, r);
    // 如果 lo 为 0，直接返回 hi 对应的前缀和
    if (lo == 0) {
        return isPrime[hi];
    }
    return isPrime[hi] - isPrime[lo - 1];
}

 int main() {
    int n = 13;
    int result = sumOfPrimesInRange(n);
    std::cout << result << std::endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。