C++で数値の奇数番目の桁の合計が素数かどうかを判定する方法

問題の概要

この問題では、ある数値 N が与えられ、その数値の奇数番目の桁（下から1桁目・3桁目・5桁目…）の合計が素数であるかどうかを判定します。

ここでいう素数判定（素数性テスト）とは、与えられた数が素数かどうかを効率的に確認するためのアルゴリズムのことです。

具体例で理解しよう

まず、例を見て問題の内容を確認しましょう。

入力：3425
出力：No
説明：奇数番目の桁の合計 = 5 + 4 = 9。9は素数ではないため「No」。

この例では、3425 の下から数えて1桁目の「5」と3桁目の「4」を足すと 9 になります。9 は 3×3 と表せるため素数ではなく、答えは「No」となります。

解法のアプローチ

この問題は、次の2ステップで簡単に解くことができます。

1. 数値を下の桁から順に走査し、奇数番目の桁だけを取り出して合計を求める
2. 求めた合計に対して素数判定を行う

C++による実装例

上記の考え方を実装したプログラムがこちらです。

サンプルコード

#include <iostream>
using namespace std;
int oddSum(int n) {
   int sum = 0, pos = 1;
   while(n) {
      if (pos %2 == 1)
         sum += n%10;
      n=n/10;
      pos++;
   }
   return sum;
}
bool isPrimeNumber(int n){
   if (n <= 1)
      return false;
   if (n <= 3)
      return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
         return false;
   return true;
}
int main() {
   int n = 1734;
   if (isPrimeNumber(oddSum(n)))
      cout<<"Sum of odd digit of the number "<<n<<" is prime Number.";
   else
      cout<<"Sum of odd digit of the number "<<n<<" is not prime Number.";
   return 0;
}

コードのポイント

• oddSum関数：数値を1桁ずつ右から処理し、奇数番目（pos が奇数）の桁のみを加算して合計を返します。
• isPrimeNumber関数：試し割り法を最適化した手法で、6k±1 の形の約数だけを調べることで高速に素数判定を行います。

実行結果

Sum of odd digit of the number 1734 is prime Number.

この例では、1734 の奇数番目の桁は「4」と「7」で、その合計は 11 になります。11 は素数であるため、「prime Number（素数である）」と出力されます。

まとめ

本記事では、数値の奇数番目の桁の合計が素数かどうかを判定するC++プログラムを紹介しました。桁の走査と素数判定という2つの基本的なアルゴリズムを組み合わせるだけで、シンプルかつ効率的に問題を解決できます。競技プログラミングや学習の練習問題としてもおすすめのテーマです。