所有因子产品的计数小于最大值

Question

我想列举一些整数因子的所有可能产品,只有一些最大值:

• P((2, 3, 11), 10)会回来的(2, 3, 4, 6, 8, 9).
• P((5, 7, 13), 30)会回来的(5, 7, 13, 25).

这似乎是树遍历,一旦达到最大值,树枝就会停止生长,但我不知道树枝数量的界限是什么.这个问题推荐使用什么算法或习惯用法？我到目前为止最接近的是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 开始的连续素数列表，这是一个平滑数字生成器。