C++でNを0に減らすために必要な特定のタイプの操作をカウントします

正の整数Nが与えられます。目標は、Nを0に減らすために必要な演算の数を見つけることです。適用される演算はN =N-Pです。ここで、PはPの最小の素数除数です。

例を挙げて理解しましょう

入力 − n =17

出力 − Nを0に減らすために必要な特定のタイプの操作の数は、− 1

説明 −17の最小の素数除数は17自体です。したがって、操作は17-17=0に1回だけ適用されます。

入力 − n =20

出力 − Nを0に減らすために必要な特定のタイプの操作の数は、− 10

説明 − 20の最小の素数の約数は2です。2を何度も減算し、次の素数の約数を見つけます：

20%2==0, 20-2=18
18%2==0, 18-2=16
…………………..14, 12, 10, 8, 6, 4, 2, 0 Total 10 times the operation is applied.

以下のプログラムで使用されているアプローチは次のとおりです

すべての偶数Nの場合、最小の素数除数は常に2になり、偶数Nから2を引くと、再び偶数になります。すべての奇数について、最小の素数除数は奇数になり、奇数から奇数を引いた後、数は偶数になるので、再び2が最小の素数になります。最小の素数除数を見つけるには、i =0からiまで、i * i

• 入力として整数Nを取ります。

• 関数N_to_Zero（int N）はNを取り、Nを0に減らすために必要な操作の数を返します。

• countの初期値を0とします。

• i=2から開始します。 （i * i）

• （i * i）がNを超える場合は、i=Nに設定します。

• 操作回数は1+（N-i）/2となります。

• カウントを1+（N-i）/2として設定します。

• 結果としてカウントを返します。

例

#include<bits/stdc++.h>
using namespace std;
int N_to_Zero(int N){
   int count = 0;
   int i = 2;
   while((i * i) < N && (N % i)){
      i++;
   }
   if((i * i) > N){
      i = N;
   }
   count = 1 + (N-i)/2;
   return count;
}
int main(){
   int N = 10;
   cout<<"Count of operations of the given type required to reduce N to 0 are: "<<N_to_Zero(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of operations of the given type required to reduce N to 0 are: 5