Hamming number search - not code or distance

Question

I am currently learning C ++.

I am looking for hamming numbers (numbers whose prime divisors are less than or equal to 5).
When I enter the number n, the program should print the nth number of hamming.

The following numbers are entered and displayed:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 ...

Finding interference numbers looks simple, but increasing the amount of input data increases exponentially overhead. If I find more 1000, he almost stands above the 1second, and more 1200, he almost costs more than a 5second.

This is the code I wrote:

while (th > 1)
{
    h++;
    x = h;

    while (x % 2 == 0)
        x /= 2;
    while (x % 3 == 0)
        x /= 3;
    while (x % 5 == 0)
        x /= 5;

    if (x == 1)
        th--;
}

So, I would like to know how to quickly find the answer. This algorithm does not seem very good.

Thanks in advance.

Answer 1

, , . , .

: 1, 2, 3 5, . , 6 2 · 3 3 · 2. .

, 32- int. , "" . , :

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

const uint umax = 0xffffffff;

void spread(std::set<uint> &hamming, uint n)
{
    if (hamming.find(n) == hamming.end()) {
        hamming.insert(n);

        if (n < umax / 2) spread(hamming, n * 2);
        if (n < umax / 3) spread(hamming, n * 3);
        if (n < umax / 5) spread(hamming, n * 5);
    }
}

int main()
{
    std::set<uint> hamming;

    spread(hamming, 1);

    std::vector<uint> ordered(hamming.begin(), hamming.end());

    for (size_t i = 0; i < ordered.size(); i++) {
        std::cout << i << ' ' << ordered[i] << '\n';
    }

    return 0;
}

, , , .

, , . h = 2^n2 + 3^n3 + 5^n5, , , :

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

int main()
{
    const uint umax = 0xffffffff;
    std::vector<uint> hamming;

    for (uint k = 1;; k *= 2) {
        for (uint l = k;; l *= 3) {
            for (uint m = l;; m *= 5) {
                hamming.push_back(m);
                if (m > umax / 5) break;
            }
            if (l > umax / 3) break;
        }
        if (k > umax / 2) break;
    }

    std::sort(hamming.begin(), hamming.end());

    for (size_t i = 0; i < hamming.size(); i++) {
        std::cout << i << ' ' << hamming[i] << '\n';
    }

    return 0;
}

break , . umax*5 , .

Koshinae , , .