C++で文字列内のASCII値が素数である文字をカウントする方法

本記事では、大文字と小文字を含む任意の長さの文字列が与えられたとき、その中でASCII値が素数となっている文字の個数を求める方法を解説します。

アルファベット大文字[A-Z]のASCII値は65〜90、小文字[a-z]のASCII値は97〜122の範囲に割り当てられています。これらの値の中には素数と非素数が混在しているため、各文字のASCII値を一つずつ判定していく必要があります。

具体例

入力 string str = "Aebg"
出力 カウント数：2

説明：「A」のASCII値は65で素数ではないためカウントされません。「e」は101で素数なのでカウントされます。「b」は66で素数ではないためカウント対象外、「g」は103で素数なのでカウントされます。したがって、ASCII値が素数である文字は合計2個となります。

入力 string str = "GOXFH"
出力 カウント数：2

説明：「G」のASCII値は71で素数のためカウントされます。「O」も79で素数のためカウントされます。一方、「X」は88、「F」は70、「H」は72といずれも素数ではないためカウントされません。結果として、ASCII値が素数の文字は合計2個となります。

プログラムのアプローチ

• 文字列を入力し、変数（例：str）に格納します。
• length()関数を使って文字列strの長さを取得します。この関数は空白を含む文字数に応じた整数値を返します。
• 各文字の判定に使用する、素数を計算する関数を宣言します。
• iを0から文字列の長さまでループさせ、文字列全体を走査します。
• ループ内で、走査中の文字のASCII値が素数かどうかを判定します。素数であればカウントを1増やし、そうでなければそのままにします。
• カウントの合計値を返します。
• 結果を出力します。

コード例

以下のコードでは、エラトステネスの篩（ふるい）を用いて、ASCII値の最大範囲をカバーする257以下の素数をあらかじめすべて求めておくことで、各文字の判定を高速に行っています。

#include <iostream>
#include <vector>
using namespace std;
#define max_val 257
// 文字列内のASCII値が素数である文字を数える関数
int countprime(string str){
    // 'max_val'以下の素数を求めるためにエラトステネスの篩を使用
    // ブール型配列 "prime[0..n]"。prime[i] の値は、
    // i が素数でなければ最終的に false、素数なら true となる。
    vector<bool> prime(max_val + 1, true);
    // 0と1は素数ではない
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= max_val; p++){
        // prime[p] が true のままなら、p は素数
        if (prime[p] == true) {
            // p のすべての倍数を false に更新する
            for (int i = p * 2; i <= max_val; i += p){
                prime[i] = false;
            }
        }
    }
    int result = 0;
    // 文字列全体を走査する
    for (int i = 0; i < str.length(); ++i){
        if (prime[int(str[i])]){
            result++;
        }
    }
    return result;
}
// main関数
int main(){
    string str = "tutorialspoint";
    // 結果を出力
    cout <<"count is: "<< countprime(str);
    return 0;
}

出力

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

count is:1

このように、エラトステネスの篩で素数表を事前に作成しておけば、文字ごとの素数判定は配列参照のみで済むため、長い文字列でも効率的に処理できます。