一个数的质因数的乘积，小于该数

Question

首先，我为标题道歉，我不知道如何用语言表达我的问题。嗯，这里是：

对于大于 1 的整数 a，设 F 为 a 的质因数的排序列表。我需要找到所有元组 c（用整数填充），这样每个元组的长度等于 F 和 (F[0] ** c[0]) * (F[1] ** c[1]) * (...) < a 的大小。我应该补充一点，我写在 Python.

示例：

a = 60
F = [2,3,5]

# expected result:

C = {(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 2, 0),
(0, 2, 1), (0, 3, 0), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1),
(1, 2, 0), (1, 3, 0), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 2, 0), (3, 0, 0),
(3, 0, 1), (3, 1, 0), (4, 0, 0), (4, 1, 0), (5, 0, 0)}

我使用 itertools.product() 生成了这个结果，特别是：

m = math.floor(round(math.log(a, min(F)), 12))
for i in itertools.product(range(m + 1), repeat=len(F)):
    if math.prod([F[j] ** i[j] for j in range(len(F))]) < a: print(i)

我认为它有效，但效率低下。例如数字 5 只出现在一个元组中，但被检查了很多次！有什么办法让它更快吗？我会使用多个 while 循环（使用 break 语句）但是因为我不知道 F 的长度是多少，我不认为这是可能。

Answer 1

您可以使用生成器遍历所有“有效”元组，如下所示：

def exponent_tuples(prime_factors, limit):
    def next_tuple(t):
        n = math.prod(f ** tt for f, tt in zip(prime_factors, t))
        for idx, (f, tt) in enumerate(zip(prime_factors, t)):
            n *= f
            if n < limit:
                return (0,) * idx + (tt + 1,) + t[idx + 1 :]
            n //= f**(tt+1)
        return None

    t = (0,) * len(prime_factors)
    while t is not None:
        yield t
        t = next_tuple(t)


for t in exponent_tuples([2, 3, 5], 60):
    print(t)

这里的想法基本上是增加元组条目，例如数字的数字，并使相应的数字滚动到零，并在达到定义的限制时携带 1。

我很确定这完全符合您的要求，除了它生成元组的顺序（可以通过修改 next_tuple 函数进行调整）

编辑：稍微简化了代码

Answer 2

你的命题不知何故变成了这个（更具可读性的形式？）

import math as m 
import pprint

a = 60
prime_factors = [2,3,5]

exponents =list(map(lambda x:m.floor(m.log(a,x)),prime_factors))
rez = []
for i in range(exponents[0]+1):
    for j in range(exponents[1]+1):
        for k in range(exponents[2]+1):
            if 2**i*3**j*5**k <= a:
                rez.append((i,j,k))
pprint.pprint(rez)

并且您想知道是否有一种方法可以使速度更快（测试更少）。所以我们不再是在实现方面，而是在概念（算法）方面？

例如，一旦选择了第一个指数 c[0]，则应在 a//(2**c[a]) 中的一个拟合中选择下一个指数，因为另一个回答者建议 i猜测

Answer 3

您的所有 range 限制仅基于 min(F)。让我们将每个自定义为 log(a, factor) 以减少大小写：

from math import ceil, log, prod
from itertools import product

a = 60
F = [2, 3, 5]

ranges = [range(0, ceil(log(a, factor))) for factor in F]

C = []

for powers in product(*ranges):
    if prod(F[i] ** power for i, power in enumerate(powers)) < a:
        C.append(powers)

print(C)

根据我的测量，您的代码生成了 216 个测试用例，得出 25 个结果，但上面的代码只生成了这些测试用例的 1/3。

Answer 4

几乎熟的提议是这样的（shell执行）

>>> max_exponents(42,[2,3,7])
[5, 3, 1]
>>> #pick 2
>>> max_exponents(42//2**2,[3,7])
[2, 1]
>>> #pick 1
>>> max_exponents(42//(2**2*3**1),[7])
[0]

我快完成了。这将适应任何数量的因素！

一个数的质因数的乘积，小于该数

Product of prime factors of a number, less than that number

python

prime-factoring

number-theory