查找在C ++中将N减少到1的最大操作
概念
对于给定的两个数P和Q（P和Q可以高达10^6），这形成一个数N=（P！/Q！）。我们的任务是通过执行尽可能多的操作将N减少到1。请记住，在每个操作中，如果N可被X整除，则可以用N/X替换N。确定可以进行的最大操作数。
输入值
A = 7, B = 4
输出结果
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的每个数字进行因子分解，计算素数的数量。
首先，使用Eratosthenes的Sieve来确定每个数字的质数。
建立一个从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开始重复。
在实施Eratosthenes的Sieve方法之后，我们可以在实施以下公式的因式分解中计算素数的数量-
primefactors[num]=primefactors[num/primedivisor[num]]+1目前，可以为素数因子实现前缀和数组，然后在区间[P，Q]上求和。
示例
// CPP program to find maximum
//可以移动号码
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
//用于存储素数
//每个数字的因素
int primeFactors1[N];
//显示查找素数的功能
//每个数字的因素
void findPrimeFactors(){
for (int a = 2; a < N; a++)
//现在，如果a是质数
if (primeFactors1[a] == 0)
for (int b = a; b < N; b += a)
//将值增加一
//简直是倍数
primeFactors1[b] = primeFactors1[b / a] + 1;
//构建前缀总和
//有帮助
//多个测试用例
for (int a = 1; a < N; a++)
primeFactors1[a] += primeFactors1[a - 1];
}
//驱动程式码
int main(){
//创建primeFactors1数组
findPrimeFactors();
int P = 7, Q = 4;
//必填
cout << primeFactors1[P] - primeFactors1[Q];
return 0;
}输出结果
4