查找最大操作以在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

    以上是 查找最大操作以在Python中将N减少为1 的全部内容, 来源链接: utcz.com/z/360078.html

    回到顶部