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 次檢視

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告