Problem29 100の100乗までの数の個数

問題

2 <= a <= 5 と 2 <= b <= 5について, aのb乗を全て考えてみよう:

2の2乗= 4 , 2の3乗=  8 , 2の4乗= 16 , 2の5乗=  32
3の2乗= 9 , 3の3乗= 27 , 3の4乗= 81 , 3の5乗= 243
4の2乗=16 , 4の3乗= 64 , 4の4乗=256 , 4の5乗=1024
5の2乗=25 , 5の3乗=125 , 5の4乗=625 , 5の5乗=3125
これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 <= a <= 100, 2 <= b <= 100 で同じことをしたとき、いくつの異なる項が存在するか?

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    const int LowerP = 2;
    //const int UpperP = 5;
    const int UpperP = 100;

    static void Main()
    {
        var JyousuuList = new List<string>();

        for (int a = LowerP; a <= UpperP; a++) {
            for (int b = LowerP; b <= UpperP; b++) {
                JyousuuList.Add(GetJyousuu(a, b));
            }
        }

        var Query = JyousuuList.Distinct()
                               .Select((X, rn) => String.Format("{0}番目は、{1}", rn + 1, X));

        foreach (string EachStr in Query) {
            Console.WriteLine(EachStr);
        }
    }

    static string GetJyousuu(int a, int b)
    {
        var WillReturn = new List<string>();

        int[] wkArr = new int[UpperP + 1];
        for (int I = 2; I <= wkArr.GetUpperBound(0); I++) {
            while (a % I == 0) {
                wkArr[I]++;
                a /= I;
            }
            wkArr[I] *= b;
        }

        for (int I = 2; I <= wkArr.GetUpperBound(0); I++) {
            if (wkArr[I] != 0) {
                WillReturn.Add(String.Format("{0}の{1}乗", I, wkArr[I]));
            }
        }

        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= WillReturn.Count - 1; I++) {
            sb.Append(WillReturn[I]);
            if (I < WillReturn.Count - 1) sb.Append("+");
        }
        return sb.ToString();
    }
}

実行結果

省略
9179番目は、2の192乗+5の192乗
9180番目は、2の194乗+5の194乗
9181番目は、2の196乗+5の196乗
9182番目は、2の198乗+5の198乗
9183番目は、2の200乗+5の200乗

解説

素因数分解の一意性を使ってます。