python - 小于最大值的所有因子产品的枚举

Question

我想枚举某些整数因子的所有可能乘积，但最多为某个最大值:

• P((2, 3, 11), 10) 将返回 (2, 3, 4, 6, 8, 9)。
• P((5, 7, 13), 30) 将返回 (5, 7, 13, 25)。

这似乎是一个树遍历， Twig 一旦达到最大值就停止生长，但我不知道 Twig 数量的界限是多少。对于这个问题推荐什么算法或成语？到目前为止我看到的最接近的是 itertools.product()，它似乎为每个输出集设置了固定数量的项(例如 2)。

对于上下文，我正在尝试检查与 n 互质的数字。在这种情况下，n 本身就是上限，因素列表是 n 的因素。我试图在上面概括一下这个问题。

Answer 1

我喜欢这种方法，它涉及将 1 乘以输入列表中的所有元素，然后将所有结果乘以输入列表中的元素，等等，直到达到限制。

def signature_seq(signature, limit):
  products = set((1,))
  for factor in signature:
    new_products = set()
    for prod in products:
      x = factor * prod
      while x <= limit:
        new_products.add(x)
        x *= factor
    products.update(new_products)

  products.remove(1)
  return products

这应该做你想做的:

>>> print(sorted(signature_seq((2, 3, 11), 10)))
[2, 3, 4, 6, 8, 9]
>>> print(sorted(signature_seq((5, 7, 13), 30)))
[5, 7, 13, 25]

顺便说一下，如果给定一个以 2 开头的连续素数列表，这是一个 smooth number发电机。