python - 这个算法会运行多少次？

Question

我在 python 中有一个函数来计算数字的质因数:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

我的问题是，程序会运行多少次才能在输入 n 时停止？如果你举一个像 56 这样的例子，我可以很容易地计算出来，但抽象地说，我似乎无法编写一个“公式”来计算在计算出所有质因数之前程序将运行多少次。

Answer 1

与其说是编程问题，不如说是数学问题，但有点有趣......

对 n 进行质因数分解形式如下:

哪里P1是最小的质因数，P2是第二小的等等，并且 Pk是最大的质因数。

需要考虑两组循环迭代:

1. 由于i而发生的循环数是 n 的质因数
2. 由于i而发生的循环数不是 n 的质因数

组 1

这个数字更容易，因为它总是相同的公式。它是质因数的每个指数之和减 1，即:

如果您考虑一下代码在 i 时的行为方式是质因数(即在将 n 除以 i 时保持循环)，指数的总和应该相当直观。您减去 1，因为最后一个追加发生在循环之外。

组 2

第二组循环稍微棘手一些，因为公式本身实际上取决于是否 az > 1 ，以及 Pk 的相对大小和P(k-1) (n 的第二小的质因数)。

如果ak > 1 ，然后是最后一个i经过循环的值是 Pk 。因此 i 的非质因子值评估的是 2 到 Pk 之间的所有数字不在集合中 P1直到Pk 。其公式如下:

记住k是 n 的不同质因数的数量。最后减去 1，因为它在 2 和 Pk 之间，不是 1 和 Pk .

另一方面，让我们考虑一下 ak = 1 的情况(ak < 1 是不可能的，因为 ak 是最大质因数的指数 - 它必须是 1 或更大)。然后i从未取过 Pk 的值，因为循环在该点之前结束，因为 while i * i <= n:情况。

那么在这种情况下， i 的最大值是多少？会采取？好吧，这取决于。

记住，如果 ak = 1 ，那么最后一个值 n采取的是Pk 。若第二大质因数P(k-1)大于 Pk 的平方根，然后一旦循环结束 i = P(k-1) ，它会立即退出循环 - 所以最大的i是 P(k-1) 。另一方面，如果 Pk 的平方根更大，那么循环将继续到该级别然后退出。那么最大的i当ak = 1等于max(P(k-1), Pk**0.5) 。这里循环次数的公式如下所示:

简化为:

请注意，我们取 Pk 平方根的下限，因为 i只会采用整数值。

一个公式...

你把它们放在一起，它会产生: