Emirp数とは？素数判定と数値反転によるEmirp数の見つけ方

Emirp数（エミルプ数）をご存知ですか？一見難しそうに聞こえますが、簡単に言うと、ある条件を満たす素数のことです。この記事では、Emirp数の定義から、それを判定するための具体的なアプローチまで、わかりやすく解説します。

Emirp数とは？定義と具体例

Emirp数とは、以下の条件を満たす素数のことを指します。

• その数自身が素数であること。
• その数の数字を反転させた数もまた素数であること。
• ただし、回文素数（例：11, 101）は除く。

例：

• 13はEmirp数です。なぜなら、13も31も素数だからです。
• 27はEmirp数ではありません。なぜなら、27は素数ではないからです。

Emirp数の判定：2つのアプローチ

Emirp数かどうかを判定する方法は主に2つあります。それぞれの方法について、詳細な手順とコード例を交えながら解説します。

アプローチ1：素数判定と反転の基本

1. 素数判定: 与えられた数が素数かどうかを判定します。 素数とは、1と自分自身以外に約数を持たない2以上の自然数です。
2. 数値反転: 与えられた数の数字を反転させます。 例えば、13であれば31に、123であれば321になります。
3. 反転後の素数判定: 反転させた数が素数かどうかを判定します。
4. Emirp数判定: 元の数と反転させた数が両方とも素数であれば、その数はEmirp数です。

以下のコードは、C++, Java, Python3, C#, Javascript, PHPによる実装例です。

C++

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
    return true;
}

bool isEmirp(int n) {
    if (isPrime(n) == false)
        return false;
    int rev = 0;
    while (n != 0) {
        int d = n % 10;
        rev = rev * 10 + d;
        n /= 10;
    }
    return isPrime(rev);
}

int main() {
    int n = 13;
    if (isEmirp(n) == true)
        cout << "Yes";
    else
        cout << "No";
}

利点:

• 理解しやすい基本的なアルゴリズム

潜在的な欠点:

• 大きな数の素数判定には時間がかかる

アプローチ2：再帰を使ったエレガントな実装

このアプローチでは、素数判定と数値反転に再帰を使用します。

1. is_prime(num) 関数: 与えられた数値が素数であるかどうかを判定します。2より小さい数値は素数ではありません。2から数値の平方根までの範囲で割り切れるかどうかを確認します。
2. reverse_number(num) 関数: 与えられた数値を反転させます。数値を文字列に変換し、文字列を反転させてから整数に戻します。
3. is_emirp(num) 関数: 与えられた数値がEmirp数であるかどうかを判定します。まず、is_prime() 関数を使用して数値が素数かどうかを確認します。素数でない場合は、「Not Emirp」を返します。次に、reverse_number() 関数を使用して数値を反転させます。反転させた数値が素数であり、元の数値と異なる場合は、「Emirp」を返します。それ以外の場合は、「Not Emirp」を返します。

以下のコードは、C++, Java, Python3, C#, Javascriptによる実装例です。

C++

#include <cmath>
#include <iostream>
#include <string>
using namespace std;

bool is_prime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int reverse_number(int num) {
    string str_num = to_string(num);
    string rev_str_num = "";
    for (int i = str_num.length() - 1; i >= 0; i--) {
        rev_str_num += str_num[i];
    }
    return stoi(rev_str_num);
}

string is_emirp(int num) {
    if (!is_prime(num)) {
        return "Not Emirp";
    }
    int rev_num = reverse_number(num);
    if (is_prime(rev_num) && num != rev_num) {
        return "Emirp";
    } else {
        return "Not Emirp";
    }
}

int main() {
    int num = 27;
    cout << is_emirp(num) << endl;
}

利点:

• 再帰的なアプローチによるコードの簡潔さ
• 平方根を用いた素数判定による効率性

潜在的な欠点:

• 再帰の理解が必要

まとめ：Emirp数判定の魅力

Emirp数の判定は、素数判定と数値反転という、プログラミングにおける基本的な要素を組み合わせた面白い問題です。この記事で紹介したアプローチを参考に、ぜひEmirp数の判定に挑戦してみてください。