C++で文字列のASCII値の合計が素数かどうかを判定する方法

この問題では、1つの文字列が与えられ、その文字列を構成する各文字のASCII値の合計が素数であるかどうかに応じて、YES / NO（素数文字列か否か）を出力することが求められます。

前提知識

ASCII値とは、コンピュータ上で文字を表現するための文字コードです。例えば、アルファベットの「A」は65、「a」は97といったように、すべての文字に固有の数値が割り当てられています。

素数とは、1とその数自身以外に正の約数を持たない数のことです。具体的には、2、3、5、7、11、13などが該当します。

問題の例

入力：string = "Hello"
出力：No

解決のアプローチ

この問題を解くための手順は以下の通りです。

まず、文字列内のすべての文字についてASCII値を取得し、その合計を計算して変数に格納します。次に、その合計値が素数であるかどうかを判定します。素数判定には、試し割り法を最適化した手法（6k±1の判定）を用いることで、効率的に処理できます。

実装コード

以下は、この解法を実装したC++のコード例です。

サンプルコード

#include <iostream>
using namespace std;
bool CheckPrimeString(string str) {
    int len = str.length(), sum = 0;
    for (int i = 0; i < len; i++)
    sum += (int)str[i];
    if (sum<= 1)
       return false;
    if (sum <= 3)
       return true;
    if (sum % 2 == 0 || sum % 3 == 0)
       return false;
    for (int i = 5; i * i <= sum; i = i + 6)
       if (sum % i == 0 || sum % (i + 2) == 0)
    return false;
    return true;
}
int main() {
    string str = "Hello!";
    cout<<"The string '"<<str<<" ' is ";
    if (CheckPrimeString(str))
       cout<<"a prime String \n";
    else
       cout<<"not a prime String\n";
}

実行結果

The string 'Hello! ' is not a prime String

コードの解説

CheckPrimeString関数では、まず文字列の長さ分だけループを回し、各文字をint型にキャストすることでASCII値を加算していきます。その後、合計値に対して以下の順序で素数判定を行います。

・合計が1以下の場合は素数ではないためfalseを返す
・合計が2または3の場合は素数であるためtrueを返す
・合計が2または3で割り切れる場合はfalseを返す
・以降は6ずつ増やしながらiとi+2で試し割りを行い、割り切れる数があればfalseを返す
・すべての判定を通過すればtrue（素数）を返す

このアルゴリズムの計算量はO(√n)であり、文字列の長さに依存せず、ASCII値の合計に対する平方根程度の計算で済むため、非常に効率的です。