在Python中查找将N减少到1的最大操作次数

假设我们有两个数字P和Q，它们构成一个数字N = (P!/Q!)。我们必须通过执行尽可能多的操作来将N减少到1。在每次操作中，当N可被X整除时，可以将N替换为N/X。我们将返回可能的最大操作次数。

因此，如果输入类似于A = 7，B = 4，则输出将为4，因为N为210，除数为2、3、5、7。

为了解决这个问题，我们将遵循以下步骤：

  • N := 1000005

  • factors := 一个大小为N的数组，并填充0

  • 从主方法中执行以下操作：

  • 对于范围从2到N的i，执行

    • 如果factors[i]等于0，则

      • 对于范围从i到N的j，每次递增i，执行

        • factors[j] := factors[j / i] + 1

  • 对于范围从1到N的i，执行

    • factors[i] := factors[i] + factors[i - 1];

  • 返回factors[a] - factors[b]

示例

让我们看看下面的实现，以便更好地理解：

 在线演示

N = 1000005
factors = [0] * N;
def get_prime_facts() :
   for i in range(2, N) :
      if (factors[i] == 0) :
         for j in range(i, N, i) :
            factors[j] = factors[j // i] + 1
   for i in range(1, N) :
      factors[i] += factors[i - 1];
get_prime_facts();
a = 7; b = 4;
print(factors[a] - factors[b])

输入

7,4

输出

4

更新于：2020年8月25日

193 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告