【C++】整数Nを0に減らすまでに必要な操作回数を求める方法

問題概要

正の整数 N が与えられます。このとき、N を 0 に減らすまでに必要な操作回数を求めるのが目標です。ここで行う操作は「N = N − P」というもので、P はその時点における N の最小の素因数を意味します。

入出力例

入力: N = 17

出力: N を 0 に減らすのに必要な操作回数: 1

説明: 17 は素数なので、最小の素因数は 17 自身です。したがって操作は 1 回だけ行われ、17 − 17 = 0 となります。

入力: 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 の順に減少し、
合計 10 回の操作が行われます。

アルゴリズムの考え方

N が偶数の場合、最小の素因数は必ず 2 であり、偶数から 2 を引いても結果は偶数のままです。一方、N が奇数の場合、最小の素因数は奇数になりますが、奇数から奇数を引くと偶数になるため、以降は再び 2 が最小の素因数となります。

この性質を利用すると、まず N の最小の素因数 i を 1 つだけ求めればよいことが分かります。i = 2 から始めて、「i × i < N かつ N % i == 0」となる i を探します。見つかった後の総操作回数は「1 + (N − i) / 2」で表されます。

• 整数 N を入力として受け取ります。
• 関数 N_to_Zero(int N) は N を受け取り、N を 0 に減らすのに必要な操作回数を返します。
• count の初期値を 0 とします。
• i = 2 から開始し、(i * i) < N かつ N が i で割り切れない間(N % i != 0)、i を 1 ずつ増やして走査します。
• (i * i) が N を超えた場合、N は素数であるため i = N とします。
• このときの操作回数は 1 + (N − i) / 2 となります。
• count に 1 + (N − i) / 2 を代入します。
• count を結果として返します。

この手法により、素因数の探索は O(√N)、残りの計算は定数時間で済むため、全体として非常に効率的に答えを求められます。

C++ 実装例

#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