问题标签 [hamming-numbers]

可能重复：
仅使用素数 2、3 和 5 生成序列，然后显示第 n 项 (C++)

我一直在头脑风暴这件事，我就是想不通。我需要解决以下问题：

生成以下序列并显示序列中的第 n 项

2,3,4,5,6,8,9,10,12,15 等.....序列只有素数 2,3,5

我需要使用基本的 C++，例如 while、for、if 等。没什么特别的。我不能简单地使用数组，因为我对它们了解不多，并且我想了解解决方案的代码。

我不是要求一个完整的解决方案，而是要求指导以解决这个问题......拜托。

我的问题是，如果序列中的数字可以被除 2、3 和 5 以外的任何其他素数整除，我不知道如何检查该数字。

另外假设我正在检查这样的数字：

它不起作用仅仅是因为它会产生诸如 14 之类的数字，它可以被质数 7 整除。所以我需要弄清楚如何确保该序列只能被 2、3 和5.....我在网上找到了很多解决问题的材料，但是他们的解决方案太先进了，我不能使用它们（而且大多数都是其他语言的......不是C++）。我敢肯定有一个更简单的方法。

我正在使用 Python 3 的功能，并尝试实现计算汉明数的经典算法。那是只有 2、3 或 5 作为素因数的数字。第一个汉明数是 2、3、4、5、6、8、10、12、15、16、18、20 等等。

我的实现如下：

合并的问题似乎不起作用。在此之前，我以同样的方式实现了埃拉托色尼筛法，并且效果非常好：

这个使用与我的合并操作相同的技术。所以我看不出有什么区别。你有什么想法？

（我知道所有这些都可以通过其他方式实现，但我的目标完全是理解 Python 的生成器和纯函数功能，包括递归，而不使用类声明或特殊的预构建 Python 函数。）

UPD：对于 Will Ness，这是我在 LISP 中实现的算法（实际上是 Racket）：

我需要定义其唯一素因数为 2、3 和 5 的数字列表，即汉明数。（即2^i * 3^j * 5^k形式的数字。序列以1、2、3、4、5、6、8、9、10、12、15、...开头）

我可以使用该factors功能或​​其他方式来做到这一点。下面factors应该返回其参数的因素。我相信我已经正确实施了它。

我尝试使用列表推导来制作 2^i * 3^j * 5^k 的列表，但在编写守卫时遇到了困难：

有一个众所周知的解决方案可以生成无限的汉明数流（即所有正整数n，其中n = 2^i * 3^j * 5^k）。我在 F# 中以两种不同的方式实现了这一点。第一种方法使用seq<int>. 解决方案很优雅，但性能很糟糕。第二种方法使用自定义类型，其中尾部包裹在Lazy<LazyList<int>>. 解决方案很笨拙，但性能令人惊叹。

有人可以解释为什么使用的性能seq<int>如此糟糕以及是否有办法解决它？谢谢。

方法 1 使用seq<int>.

方法 2 使用Lazy<LazyList<int>>.

我目前正在学习 C++。

我正在寻找汉明数（素数除数小于或等于 5 的数字）。

当我输入一个数字n时，程序应该输出第n个汉明数。

输入和输出以下数字：

找到汉明数看起来很容易，但增加输入数会成倍增加运行时间成本。

如果我输入 over 1000，它几乎花费超过1秒，而 over 1200，它几乎花费超过5秒。

这是我写的代码：

所以我想知道如何更快地找到答案。这个算法似乎不是很好。

提前致谢。

问题 - 找到只能被 2、3、5 整除的前 N ​​个数字的复杂性是多少？

我的努力

代码 -

复杂度计算-

Loop#2 复杂度- O( ln(i) )，当每个时间数都可以被 2 整除，最终达到 1 时，就会出现这种情况。

Loop#1 复杂度- O(T)，其中 T 是它迭代以获得前 N 个数字的次数。

所以复杂度是 ln(i) 的总和，其中 i = 2 到 T。

意味着，阶乘（N）与（N）^（3N/2）成正比

由上式，

问题-

1. 我们可以用 N 来表示 T 吗？
2. 如果是，那么请帮我转换它。

免责声明：有很多关于它的问题，但我没有找到任何需要恒定内存的问题。

汉明数是一个数字2^i*3^j*5^k，其中 i, j, k 是自然数。

是否有可能生成具有 O(N) 时间和 O(1)（常数）内存的第 N 个汉明数？在生成下，我的意思是生成器，即您只能输出结果而不能读取先前生成的数字（在这种情况下，内存将不是恒定的）。但是你可以保存一些固定数量的它们。

我看到只有具有恒定内存的最佳算法并不比 O(N log N) 好，例如，基于优先级队列。但是有数学证明不可能在 O(N) 时间内构建算法吗？

这是第 10 亿个丑陋/汉明数吗？

62565096724471903888424537973014890491686968126921250076541212862080934425144389 76692222667734743108165348546009548371249535465997230641841310549077830079108427 08520497989078343041081429889246063472775181069303596625038985214292236784430583 66046734494015674435358781857279355148950650629382822451696203426871312216858487 7816068576714140173718

有没有人可以分享可以验证这一点的代码？谢谢！

汉明问题是一个著名的问题，它基本上生成所有仅质因数为 {2,3,5} 的整数。（它可以扩展到我认为的任何主要因素）

为了找到第 n 个汉明数，Dijkstra 有一个巧妙的 O(N) 构造算法，其伪代码如下：

这个解的关键是，如果H是一个汉明数，那么2H、3H、5H也是一个汉明数

我遇到了一个问题，我觉得它有点像汉明问题，但它不是使用一组素因子来构造数字，而是如果我重新调整问题陈述，它就像下面这样：

1 在结果集中。如果 H 在结果集中，则 2H+1 和 3H+1 也在结果集中。在结果集中找到第 n 个数字

然后我想知道相同的构造算法是否适用于这个问题，事实证明它确实有效！（我什至不知道它为什么会起作用）

那么我想知道：

这个构造算法是否适用于生成数字的问题，给定一个规则，如“如果x在结果中，那么所有f(x), g(x), p(x), q(x)...也在结果中”，前提是这些函数将给出结果 >= x？

考虑有限集 {2,3,5,...,n}。我对素数感兴趣，但这个问题可能适用于任何一组数字。我想按升序找到这些数字的所有可能乘积，特别是大于或等于某个数字 x。有谁知道一个很好的算法吗？

编辑澄清：

输入集中的每个因子都可以使用任意次数。如果输入为 {2,3,5,7}，则输出为 {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...} . 一旦产生大于或等于某个数字 x 的结果，该算法就可以停止。