【C++】偶数位と奇数位の桁の合計の差が素数となる範囲内の数をカウントする方法

2つの整数 start と end が範囲として与えられます。この範囲 [start, end] に含まれる数の中から、「偶数位の桁の合計」と「奇数位の桁の合計」の差が素数になっている数の個数を求めるのが目的です。

つまり、(偶数位の桁の合計) − (奇数位の桁の合計) ＝ 素数 を満たす数を数えます。

具体例で理解しよう

例1

入力: 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 であり、いずれも素数です。

例2

入力: start = 1101, end = 1120

出力: 偶数位と奇数位の桁の合計の差が素数となる範囲内の数の個数: 1

説明: 1101〜1120 の範囲で条件を満たす数は以下の通りです。

1120 (3−1=2)。2は素数です。

プログラムで使用するアプローチ

ここでは動的計画法（DP）を用いて、「偶数位と奇数位の桁の合計の差が素数となる数」の個数を記録していきます。配列は arr[size][90][90][2] の形をとり、size は10の冪乗です。つまり、入力として与えられる最大の数は 10^size になります。

関数 check(int place, int eve, int od, int temp, vector<int> vec) の再帰呼び出しごとに、左から右へ0〜9の数字を配置して数を作り上げていきます。

arr[size][x][y][temp] において、x は配置済みの偶数位の桁の合計、y は配置済みの奇数位の桁の合計を表します。100以下の素数をすべて格納した配列 arr_2[] を使って、求める差が素数かどうかを判定します。

• 変数 start と end を入力として受け取ります。
• グローバル配列 arr[size][90][90][2] と、100以下の素数を格納する配列 arr_2[] を用意します。
• 関数 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 を受け取り、その各桁を LSB（最下位桁）から MSB（最上位桁）へ格納したベクター vec を生成します。
• 配列 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];
//100以下の素数
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;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

偶数位と奇数位の桁の合計の差が素数となる範囲内の数の個数: 15