【C++】配列内の「各桁の合計が素数」になる数を出力する方法

整数型の配列が与えられたとき、その要素の中から「各桁の数字を足し合わせた合計値（桁和）が素数になっている数」だけを取り出して出力するのが本記事の目的です。該当する数が一つも存在しない場合は -1 を返します。

入力と出力の例

Input: arr[]={2,4,3,19,25,6,11,12,18,7}
Output : 2, 3, 25, 11, 12, 7

この出力結果について詳しく見てみましょう。2、3、7 はそれ自体が素数であり、桁和も元の数と同じため条件を満たします。また、25（2+5=7）、11（1+1=2）、12（1+2=3）は、それぞれの桁を足した結果がいずれも素数となるため出力対象となります。

一方で、19 のように桁和が 10（1+9=10）となり素数ではない数は除外されます。4（2+2=4）、6（6）、18（1+8=9）なども同様に、数自体または桁和が素数ではないため出力されません。

アルゴリズムの手順

1. 整数型の配列とその値を用意します。
2. i、m、flag、flag1、sum、r、d、j、tem などの変数を宣言します。
3. sizeof(arr)/sizeof(arr[0]) を使って配列のサイズを m に格納します。
4. ループで配列の各要素に対して以下を繰り返します。
   • まず flag、flag1、sum を 0 に初期化します。
   • d = arr[i]/2 として、2 から d までの数で割り切れるかを確認し、割り切れる場合は flag を 1 にして素数判定を打ち切ります。
   • flag が 0（＝その数自体が素数）の場合、各桁の合計 sum を計算します。
   • さらに sum が素数かどうかを同じ要領で判定し、flag1 が 0 のままなら arr[i] を出力します。
5. すべての要素の処理が終わったら終了です。

C++での実装例

#include<iostream>
using namespace std;
int main(){
    int arr[]={2,4,3,19,25,6,11,12,18,7};
    int i,m,flag,flag1,sum,r,d,j,tem;
    m=sizeof(arr)/sizeof(arr[0]);
    for(i=0;i<m;i++) {
        flag=flag1=sum=0;
        // まず要素自体が素数かどうかを判定
        d=int(arr[i]/2);
        for(j=2;j<=d;j++){
            if(arr[i]%j==0) {
                flag=1;
                break;
            }
        }
        if(flag==0) {
            // 各桁の合計（桁和）を計算
            tem=arr[i];
            while(tem) {
                r=tem%10;
                sum=sum+r;
                tem=tem/10;
            }
            // 桁和が素数かどうかを判定
            d=int(sum/2);
            for(j=2;j<=d;j++) {
                if(sum%j==0){
                    flag1=1;
                    break;
                }
            }
            if(flag1==0){
                cout<<arr[i]<<" ";
            }
        }
    }
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

2 3 11 25 12 7

補足：処理のポイント

このプログラムでは、素数判定を行う際に「2 からその数の半分まで順番に割っていく」というシンプルな試し割り法を採用しています。より効率化したい場合は、判定範囲を √n まで縮めたり、エラトステネスの篩を使うことで計算量を大幅に削減できます。

また、桁和の計算では「10 で割った余りを取り出し、10 で割って次の桁へ進む」という定番の手法を使っている点にも注目してください。この組み合わせにより、任意の整数から簡単に桁和を求めることができます。