Problem204 一般化ハミング数

問題

ハミング数とは, どの素因数も5以下であるような正整数のことである.
最初から順に並べると, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15となる.
1億以下のハミング数は1105個ある.

素因数がn以下の正整数を, type nの一般化ハミング数と呼ぶことにする.
するとハミング数はtype 5の一般化ハミング数である.

10億以下のtype 100の一般化ハミング数の個数を答えよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    static int[] mSosuuArr;

    //エラトステネスの篩で上限以下の素数の配列を作成
    static void Eratosthenes(int pJyougen)
    {
        var IsSosuuArr = new System.Collections.BitArray(pJyougen + 1);
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
        mSosuuArr = SosuuList.ToArray();
    }

    static void Main()
    {
        Solve(100000000, 5);
        Solve(1000000000, 100);
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int ProdVal;
    }

    static void Solve(int pJyougen, int pType)
    {
        Eratosthenes(pType);

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.ProdVal = 1;
        Stk.Push(WillPush);

        int AnswerCnt = 0;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //Console.WriteLine("Type{0}のハミング数{1}を発見", pType, Popped.CurrProd);
            AnswerCnt++;

            for (int I = Popped.CurrInd; I <= mSosuuArr.GetUpperBound(0); I++) {
                WillPush.CurrInd = I;

                long wkProd = (long)Popped.ProdVal * mSosuuArr[I];
                if (wkProd > pJyougen) break;
                WillPush.ProdVal = (int)wkProd;
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine("{0}以下でType{1}のハミング数は、{2}個", pJyougen, pType, AnswerCnt);
    }
}

実行結果

100000000以下でType5のハミング数は、1105個
1000000000以下でType100のハミング数は、2944730個

解説

深さ優先探索で一般化ハミング数を列挙してます。