4

维瓦尔第数是只能被 2、3 和 5 分解的数（V = 2^a * 3^b * 5^c, a, b, c = 0,1,...也称为汉明数）。任务是找到第 N 个维瓦尔第数。

该算法对于小输入来说还不错，但 N 的范围从 0 到 9999。在 2000 年花了 2 分钟。我用一个非常简单的算法编写了代码，但我很好奇（希望）找到另一种方法。我试图用对数在数学上解决这个问题，但最终无处可去。当涉及到大量输入时，甚至可能有一种有效的方法吗？

#include <iostream>
#include <cstdlib>
#include <ctime>


bool vivaldi(unsigned long long d) {

    while (d%2 == 0)
        d = d/2;

    while (d%3 == 0)
        d = d/3;

    while (d%5 == 0)
        d = d/5;


    if (d == 1)
        return true;

    return false;
}



int main() {

    int count = 0, N;
    unsigned long long number = 0;

    std::cin >> N;

    std::clock_t begin = clock();

    if (N < 0 || N > 9999) {
        std::fprintf(stderr, "Bad input\n");
        std::exit(EXIT_FAILURE);
    }

    while (count <= N) {

        number++;
        if (vivaldi(number))
            count++;

    }

    std::cout << number << std::endl;
    std::clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    std::cout << "TIME: " << elapsed_secs << std::endl;
}
4

0 回答 0