查找最大操作以在Python中将N减少为1

假设我们有两个数字P和Q，它们形成一个数字N =（P！/ Q！）。我们必须通过执行最大数量的操作来将N减少为1。在每个操作中，当N被X整除时，可以用N / X替换N。我们将返回可能的最大操作数。

因此，如果输入像A = 7，B = 4，那么输出将是4，因为N是210，除数是2、3、5、7。

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

• N：= 1000005

• factor：=大小为N的数组，并用0填充

• 从主要方法中，执行以下操作-

• 对于2到N范围内的i

• 对于范围i至N的j，在每一步中更新i，执行

• 因素[j]：=因素[j / i] + 1

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

• 对于1到N范围内的i

• 因子[i]：=因子[i] +因子[i-1]；

• 回报因素[a]-因素[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