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 で同じことをしたとき、いくつの異なる項が存在するか?

ソース

#include <string>
#include <vector>
#include <Windows.h>
#include <valarray>
#include <algorithm>

const int LowerP = 2;
//const int UpperP = 5;
const int UpperP = 100;

std::string DeriveJyousuu(int a, int b);

void main()
{
    std::vector<std::string> JyousuuVect;
    for (int a = LowerP; a <= UpperP; a++) {
        for (int b = LowerP; b <= UpperP; b++) {
            JyousuuVect.push_back(DeriveJyousuu(a,b));
        }
    }

    std::sort(JyousuuVect.begin(),JyousuuVect.end());
    JyousuuVect.erase(std::unique(JyousuuVect.begin(),JyousuuVect.end()),JyousuuVect.end());

    int rn=0;
    for(std::vector<std::string>::iterator it=JyousuuVect.begin();it!=JyousuuVect.end();it++){
        printf("%d番目は、%s\n",++rn,it->c_str());
    }
}

std::string DeriveJyousuu(int a, int b)
{
    std::string WillReturn = "";

    std::valarray<int> JyousuuArr(0,a+1);
    for(int I=2;I<=(int)JyousuuArr.size()-1;I++){
        while (a % I == 0) {
            JyousuuArr[I]++;
            a /= I;
        }
        JyousuuArr[I] *= b;
    }

    for (int I = 2; I <= (int)JyousuuArr.size()-1; I++) {
        if (JyousuuArr[I] != 0) {
            char WKStr[100];
            wsprintf(WKStr,"%dの%d乗+",I,JyousuuArr[I]);
            WillReturn += WKStr;
        }
    }
    return WillReturn;
}

実行結果

省略
9172番目は、97の8乗+
9173番目は、97の90乗+
9174番目は、97の91乗+
9175番目は、97の92乗+
9176番目は、97の93乗+
9177番目は、97の94乗+
9178番目は、97の95乗+
9179番目は、97の96乗+
9180番目は、97の97乗+
9181番目は、97の98乗+
9182番目は、97の99乗+
9183番目は、97の9乗+

解説

素因数分解を行った結果を、string型を要素とするVectorに格納してから、
Uniqueメソッドで重複を排除し、Vectorの要素数を数えてます。