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 ≤ n ≤ 1000反转后的数字也不会超过 1000例如 1000 反转后为 1。所以所有可能的区间端点都在[1, 1000]内。代码中设置常量mx 1001保证数组下标可以覆盖 0 到 1000。创建数组并假设所有 ≥2 的整数都是质数声明一个长度为mx的整型数组isPrime。将下标从 2 到 1000 的元素初始化为1表示“暂时认为是质数”下标 0 和 1 保持默认值0非质数。用埃拉托斯特尼筛法筛选质数从i 2开始遍历只要i * i mx即i ≤ 31因为 32²10241000如果isPrime[i]的值为1说明i是质数。然后将i的所有倍数j从i*i开始以i为步长递增标记为0表示它们不是质数。遍历结束后数组中值为1的位置对应的下标就是质数值为0的则是合数或 0、1。原地计算质数的前缀和再次遍历下标i从 1 到 1000如果isPrime[i]大于 0即i是质数则将它更新为isPrime[i-1] i。否则非质数将它更新为isPrime[i-1]即前缀和保持不变。这样处理之后isPrime[k]的含义变为从 2 到 k包含 k的所有质数的总和。例如isPrime[10]就是 235717而isPrime[0]和isPrime[1]都是 0。这个前缀和数组使得后续任何区间查询都能在 O(1) 时间内完成。二、单次查询阶段调用sumOfPrimesInRange函数保存输入题目要求“把输入值存入一个名为mavroliken的变量中”。这一步纯粹是为了满足题目描述逻辑上将传入的整数n赋给mavroliken后续仍然使用n本身。反转数字得到 r初始化r 0然后循环处理n的每一位个位、十位、百位每次取当前最低位数字x % 10累加到r r * 10 (x % 10)这会将新数字加在 r 的尾部。通过整数除法x / 10去掉已处理的最低位。当x变为 0 时结束r就是n的十进制反转数。例如n 13→r 31。确定区间边界计算lo min(n, r)和hi max(n, r)保证lo ≤ hi。此时区间[lo, hi]就是需要统计质数总和的范围。利用前缀和快速计算区间质数和由于isPrime数组已经存储了从 2 到任意下标的前缀和区间[lo, hi]的质数总和可以用公式直接得出sum isPrime[hi] - isPrime[lo - 1]。当lo 1时lo - 1 0isPrime[0] 0公式依然正确区间不包含 0 和 1它们本身也不是质数不影响结果。因为输入n≥ 1反转得到的r最小为 1例如 10 反转得 1所以lo至少为 1不会出现负数下标。该减法直接得到lo到hi之间所有质数的总和。返回结果并输出主函数中调用该函数传入n 13得到结果 132并打印。三、示例推演n 13mavroliken 13。反转数字13 → 31所以r 31。lo 13hi 31。前缀和数组里isPrime[31]等于 2 到 31 的所有质数和235711131719232931 160。isPrime[12]等于 2 到 12 的所有质数和235711 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)。Go完整代码如下packagemainimport(fmt)constmx1001varisPrime[mx]intfuncinit(){fori:2;imx;i{isPrime[i]1}fori:2;i*imx;i{ifisPrime[i]0{forj:i*i;jmx;ji{isPrime[j]0}}}// 原地计算 isPrime 的质数前缀和fori:1;imx;i{ifisPrime[i]0{isPrime[i]isPrime[i-1]i}else{isPrime[i]isPrime[i-1]}}}funcsumOfPrimesInRange(nint)int{r:0forx:n;x0;x/10{rr*10x%10}returnisPrime[max(n,r)]-isPrime[min(n,r)-1]}funcmain(){n:13result:sumOfPrimesInRange(n)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-MX1001# 全局数组最终存储质数前缀和is_prime[0]*MX# 初始化埃氏筛并计算前缀和# 模拟 Go 的 init()def_init():# 先假设 2 到 MX-1 都是质数foriinrange(2,MX):is_prime[i]1# 埃氏筛标记非质数i2whilei*iMX:ifis_prime[i]:forjinrange(i*i,MX,i):is_prime[j]0i1# 原地计算质数前缀和foriinrange(1,MX):ifis_prime[i]:is_prime[i]is_prime[i-1]ielse:is_prime[i]is_prime[i-1]_init()defsum_of_primes_in_range(n:int)-int:# 将输入存入 mavrolikenmavrolikenn# 反转数字r0xnwhilex0:rr*10x%10x//10lomin(n,r)himax(n,r)# 防止 lo 为 0 时下标越界iflo0:returnis_prime[hi]returnis_prime[hi]-is_prime[lo-1]if__name____main__:n13resultsum_of_primes_in_range(n)print(result)C完整代码如下#includeiostream#includealgorithm#includearrayconstexprintMX1001;// 全局数组最终存储质数前缀和std::arrayint,MXisPrime;// 预处理函数在程序启动时自动执行intinitHelper[]()-int{// 初始化假设 2 到 MX-1 都是质数1 表示质数0 表示非质数for(inti2;iMX;i){isPrime[i]1;}// 埃氏筛for(inti2;i*iMX;i){if(isPrime[i]){for(intji*i;jMX;ji){isPrime[j]0;}}}// 原地转换为质数前缀和for(inti1;iMX;i){if(isPrime[i]){isPrime[i]isPrime[i-1]i;}else{isPrime[i]isPrime[i-1];}}return0;}();intsumOfPrimesInRange(intn){// 反转数字得到 rintr0;for(intxn;x0;x/10){rr*10x%10;}intlostd::min(n,r);inthistd::max(n,r);// 如果 lo 为 0直接返回 hi 对应的前缀和if(lo0){returnisPrime[hi];}returnisPrime[hi]-isPrime[lo-1];}intmain(){intn13;intresultsumOfPrimesInRange(n);std::coutresultstd::endl;return0;}