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

概念

对于给定的两个数字 P 和 Q（P 和 Q 最多可以是 10^6），它们构成一个数字 N = (P!/Q!)。我们的任务是通过执行尽可能多的操作来将 N 减少到 1。请记住，在每次操作中，如果 N 可以被 X 整除，则可以将 N 替换为 N/X。确定可能的最大操作数。

输入

A = 7, B = 4

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

4

解释

N 是 210，除数是 2、3、5、7

输入

A = 3, B = 1

输出

2

解释

N 是 6，除数是 2、3。

方法

已经观察到，数字 P!/Q! 的因式分解与数字 (Q + 1)*(Q + 2)*…*(P – 1)*P 的因式分解相同。

还应该注意，如果我们仅用其素因子除以 N，则操作数将最大。因此，换句话说，我们需要确定 N 的素因子的计数，包括重复的素因子。

假设计算从 2 到 1000000 的每个数字的因式分解中的素因子的数量。

首先，实现**埃拉托斯特尼筛法**来确定这些数字中每个数字的素数除数。解释如下：

  • 构建一个从 2 到 N 的连续整数列表：（2、3、4、…、N）。

  • 首先，假设 p 等于 2，即第一个素数。

  • 从 p^2 开始，以 p 为增量递增计数，并在列表中指示每个大于或等于 p^2 本身的数字。因此，这些数字可以是 p(p+1)、p(p+2)、p(p+3) 等。

  • 确定列表中大于 p 的第一个未被指示的数字。已经看到，如果没有这样的数字，则停止。否则，假设 p 现在等于此数字（表示下一个素数），并从步骤 3 再次重复。

在实现埃拉托斯特尼筛法后，我们可以使用以下公式计算因式分解中素因子的数量：

primefactors[num] = primefactors[num / primedivisor[num]] + 1 目前，可以为素因子实现前缀和数组，然后回答区间 [P, Q] 上的和。

示例

 实时演示

// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
   for (int a = 2; a < N; a++)
   // Now if a is a prime number
   if (primeFactors1[a] == 0)
      for (int b = a; b < N; b += a)
         // Now increase value by one from
         // it's preveious multiple
   primeFactors1[b] = primeFactors1[b / a] + 1;
   // Build prefix sum
   // this will be helpful for
   // multiple test cases
   for (int a = 1; a < N; a++)
      primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
   // Create primeFactors1 array
   findPrimeFactors();
   int P = 7, Q = 4;
   // required answer
   cout << primeFactors1[P] - primeFactors1[Q];
   return 0;
}

输出

4

更新于：2020-07-25

82 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告