エマープ(Emirp)とは、素数を逆転させた数もまた素数である自然数のことです。
例えば、167 は、素数ですが、これを反転した 761 も素数であり、この２つはエマープです。
Prime(素数)という単語を 反転させると Emirp になるので、そう呼ばれているそうです。
Contents
エマープを求める
さてどうやればエマープを求めることができるのでしょうか？
素数を求める
素数を逆転させる
この数も素数か？
まず素数かどうかを判定するメソッドを示します。
1は素数ではない。
2，3は素数である。
2以外の偶数は素数ではない。
2で割り切れないならそれより大きな偶数でも割り切れない（奇数で割り切れるかのみ考える）。
調べようとしている数の平方根を切り上げた整数でも割りきれない場合、それ以上大きな整数では割りきれない（もし割り切れる数が見つかるのであれば商はそれよりも小さな数になる。それが見つからなかったということは割り切れる数は存在しないということになる）のでそれ以上調べるのは時間の無駄である
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
bool IsPrime(long value) { // 1や0、負数は素数ではない if(value < 2) return false; // 2と3は素数である if(value == 2 || value == 3) return true; // 2以外の偶数であれば素数ではない if(value % 2 == 0) return false; // 平方根を切り上げた整数を求める double d = Math.Pow(value, 0.5); long max = (long)Math.Ceiling(d); // 奇数だけ平方根を切り上げた整数まで調べる for(long l = 3; l <= max; l += 2) { if(value % l == 0) return false; } // ループから抜けてしまった場合は素数である return true; } |
Reverseは数字を逆に並べ替えた数を取得するメソッドです。
|
1 2 3 4 5 6 7 |
long Reverse(long value) { char[] vs = value.ToString().ToArray(); vs = vs.Reverse().ToArray(); string str = new string(vs); return long.Parse(str); } |
IsEmirpは引数で与えられた整数がエマープかどうか判定するメソッドです。引数が素数であるなら数字を逆に並べ替え、これも素数なのか調べます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Emirp IsEmirp(long value) { bool ret = IsPrime(value); if(ret) { long reverse = Reverse(value); ret = IsPrime(reverse); if(ret) return Emirp.Emirp; else return Emirp.NotEmirp; } else return Emirp.NotPrime; } enum Emirp { Emirp, // エマープである NotEmirp, // 素数ではあるがエマープではない NotPrime, // 素数ですらない } |
GetEmirpsはエマープを取得するメソッドです。minは調査を開始する最小値、countは取得したいエマープの個数です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
List<long> GetEmirps(int min, int count) { List<long> vs = new List<long>(); int cnt = 0; for(long value = min; ; value += 2) { if(IsEmirp(value) == Emirp.Emirp) { vs.Add(value); if(++cnt > count -1) break; } } return vs; } |
ボタンをクリックしたらエマープかどうか調べて10,000個取得し、これを文字列に変換します。これをリッチテキストボックスに表示させます。
一桁なら並べ替えても同じなので11から調べています。10,000個取得であればすぐにおわります。10,000番目のエマープは942,811です。100,000個取得しようとすると時間がかかります。ネットショップで中古で購入したパソコン（X230）では17秒かかりました。100,000番目のエマープは11,240,387です。
|
1 2 3 4 5 6 7 |
private void button1_Click(object sender, EventArgs e) { List<long> vs = GetEmirps(11, 10000); string[] ar = vs.Select(x => x.ToString("#,0")).ToArray(); string str = String.Join("\n", ar); richTextBox1.Text = str; } |
回文素数を求める
エマープと回文数になっている素数を合わせたもの（つまり、逆から読んでも素数である素数全体）を回文素数と呼ばれることがあります。回文素数も求めてみましょう。
IsPalindromesは回文数かどうか調べるメソッドです。
|
1 2 3 4 |
bool IsPalindromes(long value) { return Reverse(value) == value; } |
IsPalindromesPrimeは回文素数かどうかを調べるメソッドです。まず回文数かどうか調べて、そのあと素数かどうかを調べます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
PalindromesPrime IsPalindromesPrime(long value) { bool ret = IsPalindromes(value); if(ret) { ret = IsPrime(value); if(ret) return PalindromesPrime.PalindromesPrime; else return PalindromesPrime.NotPrime; } else return PalindromesPrime.NotPalindromes; } enum PalindromesPrime { PalindromesPrime, // 回文素数である NotPrime, // 回文数だが素数ではない NotPalindromes, // 回文数ですらない } |
GetPalindromesPrimesは回文素数を取得するメソッドです。minは調査を開始する最小値、countは取得したい回文素数の個数です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
List<long> GetPalindromesPrimes(int min, int count) { List<long> vs = new List<long>(); int cnt = 0; for(long value = min; ; value += 2) { if(IsPalindromesPrime(value) == PalindromesPrime.PalindromesPrime) { vs.Add(value); if(++cnt > count - 1) break; } } return vs; } |
一桁なら回文にはならないので11から調べています。今度は10,000個取得しようとしても相当な時間が必要になりそうです。500個であればすぐに終わりますが、1,000個取得しようとしてもなかなか終わりません。取得できるまでに約60秒かかりました。1,000番目の回文素数は114,494,411です。
100,000番目のエマープが11,240,387であることと比較すると時間がかかるのもわかるような気がします。
|
1 2 3 4 5 6 7 |
private void button2_Click(object sender, EventArgs e) { List<long> vs = GetPalindromesPrimes(11, 1000); string[] ar = vs.Select(x => x.ToString("#,0")).ToArray(); string str = String.Join("\n", ar); richTextBox1.Text = str; } |
