Python，哈明数解释

Question

我在做一个编程题目，需要写一个函数来找出第n个汉明数。

我写了一段代码，先创建一个大小为n的列表，列表里的每个值都是“1”，然后通过一些操作来改变列表中的值，使得每个值都是汉明数。

代码如下：

def hamming(num):
  #Make a list of size n, n-1 is the value we want to return.
  h = [1] * num

  #Make 3 variables representing the 2^i, 3^j, 5^k of our hamming number.
  x2, x3, x5 = 2,3,5

  #Counter variables that we will raise 2, 3, and 5, to.
  i = j = k = 0

    #Our initial list is filled with n values of the integer 1.
  for n in xrange(1, num):
    #Get the smallest number, then we will multiply it by 2, 3, or 5.
    h[n] = min(x2, x3, x5)
    if x2 == h[n]:
      i += 1
      x2 = 2 * h[i]
    if x3 == h[n]:
      j += 1
      x3 = 3 * h[j]
    if x5 == h[n]:
      k += 1
      x5 = 5 * h[k]
  return h[-1]

其实，我想问的不是这种生成汉明数的方法是怎么工作的，而是为什么这样做能得到汉明数。比如，128是一个汉明数，而2^7 * 3^0 * 5^0也等于128。但是，因为7不是汉明数，而这个方法是用列表中之前计算的值来生成汉明数的，所以我想知道为什么在任何汉明数用2^i * 3^j * 5^k表示时，i、j或k不需要是汉明数也能生成汉明数。

如果我的问题让你感到困惑，抱歉。如果你需要我解释得更清楚一点，请告诉我，我会尽量解释得更好。

Answer 1

汉明数是指只有2、3和5这几个质因数的数字。

引用一下维基百科上的内容：

在数论中，这些数字被称为5-平滑数，因为它们的质因数只有2、3或5。

你可能想了解一下质因数是什么，以及它们是怎么工作的。简单来说，质因数就是如果你把它乘够多次，就能得到你原来的数字。质因数是最小的乘数（因为质数是最小的数，不能再小了）。

举个例子，如果你有数字12，12可以被6、4、3和2整除。在这四个因数中，有两个不是质数，所以可以继续拆分。6可以被2和3整除，而4可以被2整除。因此，我们的质因数就是2和3。

你的代码是把汉明数的质因数分别提升到i、j和k的幂次。幂次的具体值并不重要，只要质因数是对的就行。所以，你可以用2^7得到汉明数128，尽管7本身不是汉明数，因为关键是2。例如，2^7其实就是2乘以自己7次。所以7并不真正参与。你最开始的列表只是一些随机整数，和汉明数没有关系。2、3和5才是关键。