C++でNを1に減らすための最大操作を見つける

コンセプト

与えられた2つの数PとQ（PとQは最大10 ^ 6）に関して、数N =（P！/ Q！）を形成します。私たちのタスクは、可能な最大数の操作を実行することにより、Nを1に減らすことです。 NがXで割り切れる場合は、各操作でNをN/Xに置き換えることができます。可能な操作の最大数を決定してください。

入力

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までのすべての数の因数分解で素因数の数を数えると仮定します。

まず、エラトステネスのふるいを実装します これらの数のそれぞれの素数の約数を決定します。これは次のように説明されます-

• 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