Project Euler : Problem 26 『Reciprocal cycles』

Geometric Tiles, Mosque of Moulay Idriss, Morocco / Dimitry B

問題

projecteuler.net

最も循環節が長くなる1/dのd (d < 1000) を求めよ。

困った時のwikipedia

　昔、循環小数を100まで出力したことがあった。
pongeponge.hatenablog.jp
似たような方法を使おうかと思ったけど、どうにも時間かかりすぎる気がしたので却下。

　つらつらと見てると、素数の時に長い循環節が出てくる傾向があるのに気づく。
でも気づいたのはそれだけで、それ以外の循環節の長さと数の関係がわからないのでWikipediaで調べることに。

　2 と 5（一般には、基数の約数たる素数）以外の素数 p の逆数の循環節の長さは、p － 1 の約数である。
循環小数 - Wikipedia

　へー。

私の方法

(1) 素数のリストを作る
(2) 大きい素数pからピックアップ
(3) 10ⁿをpで割った余りが1になるまでnを増やす
(4) 余り1になれば、その時点のnが1/pの循環節の長さL
(5)Lよりp-1の約数が小さければ、それ以降のpは計算しない

コード

using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;

namespace Problem26
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine("RC1:" + ReciprocalCycles(1000));
        }

        static int[] CreatePrimeArray(int max)
        {
            List<int> p = new List<int>();

            for (int i = 0; i <= max; i++)
            {
                p.Add(i);
            }

            for (int i = 2; i <= max / 2; i++)
            {
                if (p[i] != 0)
                {
                    for (int j = 2; p[i] * j <= max; j++)
                    {
                        p[i * j] = 0;
                    }
                }
            }

            p.RemoveAll(obj => obj == 0);

            //1,2,5は巡回小数にならないので最初に削除しておく
            p.RemoveAt(3);
            p.RemoveAt(1);
            p.RemoveAt(0);

            return p.ToArray();
        }

        static int ReciprocalCycles(int max)
        {
            int[] primes = CreatePrimeArray(max);

            int l = 0;
            int n = 0;

            for (int i = primes.Length-1; i >= 0; i--)
            {
                for (int d = primes[i].ToString().Length; ; d++)
                {
                    if (Pow(d) % primes[i] == 1)
                    {
                        if (l < d)
                        {
                            l = d;
                            n = primes[i];
                        }
                        break;
                    }
                }

                if (primes[i] - 1 < l) break;
            }

            return n;
        }

        static BigInteger Pow(int y)
        {
            BigInteger p = 1;

            for (int i = 0; i < y; i++)
            {
                p *= 10;
            }

            return p;
        }
    }
}