C++中计算范围内的数字，其偶数位和奇数位数字之和的差为素数

给定两个数字start和end作为范围变量。目标是找到在这个范围[start,end]内，且偶数位数字和与奇数位数字和的差为素数的数字个数。

也就是说，（偶数位数字和） - （奇数位数字和）= 素数

让我们通过例子来理解。

例如

输入 - start = 230, end = 270

输出 - 偶数位和与奇数位和的差为素数的数字个数为：6

解释 - 在230到270之间的满足条件的数字是

240 (4-2 = 2), 250 (5-2 = 3), 251 (5-3 = 2), 261 (6-3 = 3), 262 (6-4 = 2), 270 (7-2 = 5)。

这些差值都是2、3和5，都是素数。

输入 - start = 1101, end = 1120

输出 - 偶数位和与奇数位和的差为素数的数字个数为：1

解释 - 在1101到1120之间满足条件的数字是

1120 (3-1 = 2)。2是素数。

下面程序中使用的算法如下

在这个程序中，我们使用动态规划的方法，存储具有素数差（偶数位数字和与奇数位数字和的差）的数字个数。这个数组将是arr[size][90][90][2]。这里size是10的幂。因此，最大的输入数字将是10size。

在对函数check(int place, int eve, int od, int temp, vector<int> vec)的每次递归调用中，我们将从左到右放置数字0到9来构建一个数字。

在arr[size][x][y][temp]中，x是直到x位置偶数位数字的和，y是直到y位置奇数位数字的和。使用存储所有小于100的素数的数组arr_2[]检查所需的差是否为素数。

  • 将变量start和end作为输入。
  • 使用全局数组arr[size][90][90][2]和数组arr_2[]存储小于100的素数。
  • 函数check(int place, int eve, int od, int temp, vector<int> vec)将当前数字位置作为place，当前偶数位数字和作为eve，奇数位数字和作为od，temp的值以及包含数字的向量vec作为参数。
  • 它递归地填充arr[place][eve][od][temp]中的值。
  • 将当前元素的初始值设置为count=0。
  • 对于当前位置，使用if(place == vec.size())检查是否为最后一位。如果是，则检查该位置是奇数位还是偶数位。
  • 如果if(vec.size() & 1)结果为真，则当前位置为奇数位，因此交换eve和od，因为它是一个奇数长度的数字。
  • 计算temp_2作为eve-od的差值。
  • 使用for循环遍历arr_2[]并检查是否找到temp_2。如果是，则它是素数。因此返回1，否则返回0。
  • 如果arr[place][eve][od][temp]已经被计算，则它将不为-1，因此返回它。
  • 如果temp不为零，则设置temp_3=9。Temp_3是我们可以放置的数字的最大限制。如果它是0，则放置vec[place]，否则数字已经更小，所以放置任何数字，例如9。
  • 遍历从0到temp_3的数字。如果当前位置是奇数位，则更新set_odd = set_odd + i;（之前的奇数位数字和 + 当前数字i）。
  • 如果当前位置是偶数位，则更新set_even = set_even + i;（之前的偶数位数字和 + 当前数字i）。
  • 设置count += check(place + 1, set_even, set_odd, set_temp, vec);并返回arr[place][eve][od][temp] = count。
  • 函数place_prime(int val)获取数字val并生成一个向量vec，其中包含从LSB到MSB的数字。
  • 将整个数组arr[][][][]设置为-1。
  • 设置count = check(0, 0, 0, 0, vec)，它将在最后返回结果。
  • 返回count作为结果。

示例

在线演示

#include <bits/stdc++.h>
using namespace std;
const int size = 18;
int arr[size][90][90][2];
//firt 100 prime Numbers
int arr_2[] = {
   2,
   3,
   5,
   7,
   11,
   13,
   17,
   19,
   23,
   29,
   31,
   37,
   43,
   47,
   53,
   59,
   61,
   67,
   71,
   73,
   79,
   83,
   89,
   97
};

int check(int place, int eve, int od, int temp, vector < int > vec) {
   int count;
   int temp_3;
   if (place == vec.size()) {
      if (vec.size() & 1) {
         swap(od, eve);
      }
      int temp_2 = eve - od;
      for (int i = 0; i < 24; i++) {
         if (temp_2 == arr_2[i]) {
            return 1;
         }
      }
      return 0;
   }
   if (arr[place][eve][od][temp] != -1) {
      int set = arr[place][eve][od][temp];
      return set;
   }
   if (temp) {
      temp_3 = 9;
   } else {
      temp_3 = vec[place];
   }
   for (int i = 0; i <= temp_3; i++) {
      int set_temp = temp;
      int set_even = eve;
      int set_odd = od;
      if (i < vec[place]) {
         set_temp = 1;
      }
      if (place & 1) {
         set_odd = set_odd + i;
      } else {
         set_even = set_even + i;
      }
      count += check(place + 1, set_even, set_odd, set_temp, vec);
   }
   return arr[place][eve][od][temp] = count;
}

int place_prime(int val) {
   vector < int > vec;

   while (val) {
      vec.push_back(val % 10);
      val = val / 10;
   }
   reverse(vec.begin(), vec.end());
   memset(arr, -1, sizeof(arr));
   int count = check(0, 0, 0, 0, vec);
   return count;
}
int main() {
   int start = 20, end = 80;
   int count = place_prime(end) - place_prime(start - 1);
   cout << "Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: " << count;
   return 0;
}

如果我们运行上面的代码，它将生成以下输出：

输出

Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15

更新于：2021年1月29日

223 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告