C ++の素数として、偶数と奇数の桁の合計の差がある範囲内の数値をカウントします

範囲変数として開始と終了の2つの数値が与えられます。目標は、この範囲[開始、終了]にあり、プライムとして偶数の桁の合計と奇数の位置の桁の合計の差がある数値の数を見つけることです。

つまり、（偶数の位置の桁の合計）-（奇数の位置の桁の合計）=素数

例を挙げて理解しましょう。

例

入力- 開始=230、終了=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です。

入力- 開始=1101、終了=1120

出力- 素数としての偶数と奇数の桁の合計の差がある範囲内の数値の数は次のとおりです：1

説明- 条件を満たす1101から1120までの番号は次のとおりです。

1120（3-1は2）。 2は素数です。

以下のプログラムで使用されているアプローチは次のとおりです

これでは、動的計画法のアプローチを使用して、偶数と奇数の桁の合計の素数の差がある数値のカウントを格納します。この配列はarr[size][90][90][2]になります。ここで、サイズは10の累乗です。したがって、入力としての最大数は10 ^サイズ になります。 。

関数check（int place、int eve、int od、int temp、vector vec）を再帰的に呼び出すたびに、0から9までの数字を左から右に配置して数値を作成します。

arr [size] [x] [y] [temp]では、xはxまでの偶数位置の桁の合計を表し、yはyまでの奇数桁の合計を表します。必要な違いが素数であるかどうか、または100までのすべての素数を順番に格納する配列arr_2[]を使用していないかどうかを確認します。

• 変数の開始と終了を入力として受け取ります。
• 100までの素数の場合はグローバル配列arr[size][90][90][2]と配列arr_2[]を使用します。
• 関数check（int place、int eve、int od、int temp、vector vec）は、桁の現在の位置を場所として、前夜の位置の桁の現在の合計を偶数として、奇数の位置の桁をodとして、tempの値を取ります。数字を持つベクトルvec。
• arr [place] [eve][od][temp]に再帰的に値を入力します。
• 現在の要素の初期値をcount=0とします。
• 現在の位置については、if（place ==vec.size（））を使用して場所が最後の位置であるかどうかを確認します。はいの場合、その位置が奇数か偶数かを確認します。
• if（vec.size（）＆1）の結果がtrueの場合、現在の位置は奇数です。奇数の長さの数値であるため、eveをodと交換してください。
• temp_2を前夜の合計の差として計算します。
• 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）。
• カウントの設定+=check（place + 1、set_even、set_odd、set_temp、vec）; arr [place] [eve] [od] [temp]=countを返します。
• 関数place_prime（int val）は、数値valを受け取り、LSBからMSBまでの数字を含むベクトルvecを生成します。
• 配列全体のarr[][][][]を-1に設定します。
• count =check（0、0、0、0、vec）を取得すると、終了時に結果が返されます。
• 結果としてカウントを返します。

例

#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