UVa 136

Ugly Numbers.cpp

#include <cstdio>
#include <vector>

void tryDivide(const std::vector<int> &baseList, int &number)
{
    const auto endIndex = static_cast<int>(baseList.size()) - 1;
    for (auto i = endIndex - 1; i >= 0;)
    {
        if (number == 1)
        {
            break;
        }

        if (number % baseList[i] == 0)
        {
            number /= baseList[i];
        }
        else
        {
            i--;
        }
    }
}

int main()
{
    auto T = 0;
    auto base2List = std::vector<int>{2, 4, 16, 256, 65536};
    auto base3List = std::vector<int>{3, 9, 81, 6561, 43046721};
    auto base5List = std::vector<int>{5, 25, 625, 390625};
    for (auto i = 1;; i++)
    {
        auto number = i;
        tryDivide(base2List, number);
        tryDivide(base3List, number);
        tryDivide(base5List, number);

        if (number == 1)
        {
            T++;
            printf("%d %d\n", i, T);
        }
    }
}