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

概念

对于给定的两个数P和Q（P和Q可以高达10 ^ 6），这形成一个数N =（P！/ Q！）。我们的任务是通过执行尽可能多的操作将N减少到1。请记住，在每个操作中，如果N可被X整除，则可以用N / X替换N。确定可以进行的最大操作数。

输入值

A = 7, B = 4

输出结果

说明

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

输入值

A = 3, B = 1

输出结果

说明

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;
}

输出结果

基础教程