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

  • 0
    Like
  • 0
    Comment
    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 RevString(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で公開したものを加筆・修正したものです。