Help us understand the problem. What is going on with this article?

C#:エマープでかつ上昇数を求める

More than 1 year has passed since last update.

エマープでかつ上昇数とは

素数を逆転させた数もまた素数である自然数のことを 「エマープ(Emirp)」と言います。

例えば、167 は、素数ですが、これを反転した 761 も素数であり、この2つはエマープです。 Prime(素数)という単語を 反転させると Emirp になるので、そう呼ばれているそうです。

また、1479のように、左から右へどんどん大きな数字になってゆく数を、ここでは「上昇数」と呼ぶことにします。

エマープでかつ上昇数を求めるには

さて、エマープでかつ上昇数を求める方法ですが、 1 から 123456789 までのすべての数字に対して、一つずつ条件を満たすかを調べていては 効率が悪すぎます。

そのため、「全ての上昇数を求め、それが、エマープかどうかを調べる」という方法で、答えを見つけることとします。

C#のコード

RisingEmirpNumbers.cs
    class Program {
        static void Main(string[] args) {
            var solver = new RisingEmirpNumbers();
            foreach (var n in solver.Solve().OrderBy(s => s.Length))
                Console.WriteLine(n);
        }
    }

    public class RisingEmirpNumbers {
        // 問題を解く 答えは文字列として列挙する
        public IEnumerable<string> Solve() {
            int[] nums = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            foreach (var s in GetRisingNumbers("", nums)) {
                if (IsEmirp(s))
                    yield return s;
            }
        }

        // 上昇数 を求める 再帰メソッドの中で、yield return を使っている。
        private IEnumerable<string> GetRisingNumbers(string rn, IEnumerable<int> nums) {
            if (nums.Count() == 0)
                yield break;
            int i = 0;
            foreach (var n in nums) {
                i++;
                string s = rn + n.ToString();
                yield return s;
                foreach (var r in GetRisingNumbers(s, nums.Skip(i)))
                    yield return r;
            }
        }

        // エマープか?
        private bool IsEmirp(string s) {
            if (s.Length >= 2 &&
                PrimeNumber.IsPrime(long.Parse(s)) &&
                PrimeNumber.IsPrime(long.Parse(ReverseString(s))))
                return true;
            return false;
        }

        // 文字列を反転する
        private string ReverseString(string s) {
            return new string(s.Reverse().ToArray());
        }
    }

上記コードの説明を簡単にします。

Solveメソッド

エマープでかつ上昇数をすべて列挙するメソッドです。このメソッドは、上昇数を列挙し、その値が、エマープかどうかを調べています。

GetRisingNumbersメソッド

上昇数を列挙するメソッドです。IEnumerable<string> 型を返す再帰メソッドとなっています。 メソッドの第1引数には、上昇数の途中結果が渡されます。初期値は 空文字列です。 第2引数には、上昇数で利用できる数字が小さい順に格納されている IEnumerable<int> 型です。 初期値は、 { 1,2,3,4,5,6,7,8,9 } です。

例えば、第1引数に "24" という文字列が渡された時には、 第2引数には、{ 5,6,7,8,9 } が渡されます。

再帰メソッドで、IEnumerable<T> を戻り値にする方法については、僕のブログの記事「再帰メソッドで、yield returnしたい」を読んでください。

IsEmirpメソッド

素数判定は、「ミラー・ラビン素数判定法による素数判定メソッド」で示したクラスを使って素数判定をしています。この PrimeNumber.IsPrimeメソッドと下記の文字列を反転するReverseStringを使い、エマープかどうかを判定しています。

ReverseStringメソッド

LINQの Reverse拡張メソッドを利用し反転させ、文字列に変換しています。
これを拡張メソッドとして定義すれば、 string rs = s.ReverseString(); なんて書けますね。

これらのメソッドができあがれば、Solveメソッドを書くのは簡単ですね。

結果

上記コードを実行した結果(エマープでかつ上昇数の一覧)です。

13
17
37
79
149
157
167
179
347
359
389
1237
1249
1259
1279
1789
3467
3469
12689
13457
13469
13789
15679
34589
345689
1235789

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした