【C++入門】エマープ数（Emirp）とは？n以下のエマープ数をすべて出力するプログラム

エマープ数（Emirp number）とは、素数の一種で、その桁を逆順に並べ替えると別の素数になる数のことです。ここでいう「別の素数」とは、元の数と同じ値にならないものを指します。

Emirpは「prime（素数）」を逆から読んだ言葉

すべての素数がエマープ数になるわけではありません。たとえば、回文素数（121のように逆から読んでも同じ数になる素数）や、1桁の素数（2、3、5、7）は、桁を逆にしても同じ数または意味を持たないため、エマープ数には含まれません。

エマープ数の例：13、17、37、733 などがあります。

• 13 を逆にすると 31（素数）→ エマープ数
• 17 を逆にすると 71（素数）→ エマープ数
• 37 を逆にすると 73（素数）→ エマープ数

n以下のエマープ数をすべて出力するプログラム

ここでは、ある数 n が与えられ、n以下のすべてのエマープ数を出力することを目標とします。

具体的な例で問題を確認してみましょう。

入力： n = 40

出力： 13、17、31、37

解決アプローチ

与えられた数以下のすべてのエマープ数を見つけるには、次の手順で処理を行います。

1. n以下のすべての素数を求める。
2. 各素数について、桁を逆順に並べ替えた数を作る。
3. 逆順の数が元の数と異なり、かつ素数であれば、それはエマープ数なので出力する。

nまでの素数を効率よく求め、さらにその逆順の数が素数かどうかを再確認するには、エラトステネスの篩（ふるい）を使うのが最適な方法です。このアルゴリズムを使えば、高速に素数表を作成できます。

解法の動作を示すプログラム

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int reverseDigits(int x) {

    int digitRev = 0;
    while (x > 0)
    {
        digitRev = (digitRev*10) + x%10;
        x = x/10;
    }
    return digitRev;
}

void findAllEmirpNumber(int n) {

    bool primeNo[10001];
    memset(primeNo, true, sizeof(primeNo));

    for (int p=2; p*p<=10001; p++)
    {
        if (primeNo[p] == true)
        {
            for (int i=p*2; i<=10001; i += p)
                primeNo[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
    {
        if (primeNo[p])
        {
            int revNo = reverseDigits(p);
            if (p != revNo && primeNo[revNo]) {
            cout<<p<<"\t";
            if(revNo <= n)
             cout<<revNo<<"\t";
            primeNo[revNo] = false;
            }
        }
    }
}

int main()
{
    int n = 40;
    cout<<"All Emirp numbers less than or equal to "<<n<<" are\n";
    findAllEmirpNumber(n);
    return 0;
}

実行結果

All Emirp numbers less than or equal to 40 are 13 31 17 37

コードのポイント

• reverseDigits関数： 数値の桁を逆順に並べ替えた整数を返します。剰余演算（%）と除算（/）を繰り返すことで実現しています。
• findAllEmirpNumber関数： エラトステネスの篩で素数表を作成した後、各素数の逆順の数も素数かどうかをチェックし、エマープ数だけを出力します。
• 重複防止： 一度出力したペア（例：13と31）を再度出力しないよう、フラグをfalseに設定して管理しています。