Problem73 ある範囲内の分数の数え上げ

問題

nとdを正の整数として, 分数 n/d を考えよう.
n<d かつ HCF(n,d) = 1のとき、真既約分数と呼ぶ.

d <= 8 について真既約分数を大きさ順に並べると, 以下を得る:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2,
4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

1/3と1/2の間には3つの分数が存在することが分かる.
では, d <= 12000 について真既約分数をソートした集合では,
1/3 と 1/2 の間に何個の分数があるか?

ソース

using System;

class Program
{
    //const int MaxD = 8;
    const int MaxD = 12000;

    static void Main()
    {
        int AnswerCnt = 0;

        for (int D = 1; D <= MaxD; D++) {
            int MinVal = DeriveMinSeisuuKai(D);
            int MaxVal = DeriveMaxSeisuuKai(D);

            if (MaxVal == 0) continue;

            for (int N = MinVal; N <= MaxVal; N++) {
                //分子と分母が互いに素なら既約分数
                if (DeriveGCD(D, N) == 1) {
                    AnswerCnt++;

                    if (D > 8) continue;
                    Console.WriteLine("解{0}を発見。1/3 < {1}/{2} < 1/2", AnswerCnt, N, D);
                }
            }
        }
        Console.WriteLine("答えは{0}", AnswerCnt);
    }

    //分母を引数として、不等式 分子/分母 > 1/3 の最小の整数解を求める
    static int DeriveMinSeisuuKai(int pBunbo)
    {
        return pBunbo / 3 + 1;
    }

    //分母を引数として、不等式 分子/分母 < 1/2 の最大の整数解を求める
    static int DeriveMaxSeisuuKai(int pBunbo)
    {
        bool NeedKurisage = (pBunbo % 2 == 0);
        int WillReturn = pBunbo / 2;
        return (NeedKurisage ? WillReturn - 1 : WillReturn);
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static int DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = Math.Max(pVal1, pVal2);
        int WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            int Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

実行結果

解1を発見。1/3 < 2/5 < 1/2
解2を発見。1/3 < 3/7 < 1/2
解3を発見。1/3 < 3/8 < 1/2
答えは7295372

解説

分母ごとに
不等式 分子/分母 < 2/1 の最大の整数解と、
不等式 分子/分母 > 3/1 の最小の整数解を求めてから、
真既約分数の数を数えてます。