C#:二乗して回文となる非回文数を求める

  • 0
    いいね
  • 1
    コメント

    二乗すると回文数となる数で、二乗する前の数が回文でない正の整数を求めるプログラムを書いてみました。

    回文数とは、21512 のように、逆から読んでも同じ数になる数字のことです。

    C#のコード

    PalindromicSquare.cs
        class Program {
            static void Main(string[] args) {
                using(new Timewatch()) { 
                    var solver = new PalindromicSquare();
                    foreach (vae n in solver.Solve(100000000)) {
                        Console.WriteLine($"{n} * {n} = {(long)n * n}");
                    }
                }
    
            }
        }
    
        public class PalindromicSquare {
            private bool IsPalindrome(long num) {
                string s = num.ToString();
                int len = s.Length;
                int rx = len - 1;
                int lx = 0;
                while (lx < len / 2)
                    if (s[lx++] != s[rx--])
                        return false;
                return true;
            }
    
            public IEnumerable<int> Solve(int maxnum) {
                for (var i = 1; i <= maxnum; i++) {
                    if (IsPalindrome((long)i * i) && !IsPalindrome(i))
                        yield return i;
                }
            }
        }
    

    PalindromicSquareクラスがその解を求めるクラスで、Solveメソッドは、IEnumerabl<int>を返すメソッドとしています。

    少しでも速くなるように、回文かどうかを判定するIsPalindromeでは、文字列を反転させ比較するのではなく、文字列の両端から内側に向かって比較するようにしています。

    また、Solveメソッドの中では、IsPalindrome((long)i * i)IsPalindrome(i)よりも先に呼び出すようにしています。

    iが非回文である確率よりもi * iが回文となる確率の方が低いはずですから、以下のコードよりもメソッドの呼び出し回数が減り多少速くなります。

          if (!IsPalindrome(i) && IsPalindrome((long)i * i))
              yield return i;
    

    このプログラムでは、100000000以下の値を対象にしました。
    手元のPCだと、30秒弱で答えが求まりました。

    これよりも大きな値を対象にすると、もっと速度を上げる必要がありますが、処理速度を上げるには根本的にアルゴリズムを考え直す必要がありそうです。
    残念ながら、その答えを持ち合わせていません。

    Solveメソッドは(IsPalindromeも含めて)、LINQ使えば、もっと簡潔に書けると思います。

    結果

    
    26 * 26 = 676
    264 * 264 = 69696
    307 * 307 = 94249
    836 * 836 = 698896
    2285 * 2285 = 5221225
    2636 * 2636 = 6948496
    22865 * 22865 = 522808225
    24846 * 24846 = 617323716
    30693 * 30693 = 942060249
    798644 * 798644 = 637832238736
    1042151 * 1042151 = 1086078706801
    1109111 * 1109111 = 1230127210321
    1270869 * 1270869 = 1615108015161
    2012748 * 2012748 = 4051154511504
    2294675 * 2294675 = 5265533355625
    3069307 * 3069307 = 9420645460249
    11129361 * 11129361 = 123862676268321
    12028229 * 12028229 = 144678292876441
    12866669 * 12866669 = 165551171155561
    30001253 * 30001253 = 900075181570009
    64030648 * 64030648 = 4099923883299904
    

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