我目前正在学习C++。
我正在寻找Hamming numbers(其质因子小于或等于5的数值)。
当我输入一个数字n时,程序应该输出第n个Hamming数。
以下是输入和输出的数字:
找到汉明数看起来很容易,但增加输入数字会使运行时间成本呈指数增长。
如果我输入超过1000,它几乎需要超过1秒的时间, 而超过1200,它几乎需要超过5秒的时间。
这是我写的代码:
我正在寻找Hamming numbers(其质因子小于或等于5的数值)。
当我输入一个数字n时,程序应该输出第n个Hamming数。
以下是输入和输出的数字:
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 ...
找到汉明数看起来很容易,但增加输入数字会使运行时间成本呈指数增长。
如果我输入超过1000,它几乎需要超过1秒的时间, 而超过1200,它几乎需要超过5秒的时间。
这是我写的代码:
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--;
}
我想知道如何更快地找到答案。这个算法似乎不太好。
提前感谢。