C++でLCMをNとして使用した個別の数値の最大合計

この問題では、数値Nが与えられます。私たちのタスクは、C++でLCMをNとして使用して個別の数値の最大合計を見つけるプログラムを作成することです。

問題の説明

ここでは、最小公倍数（LCM）としてNを持つ最大数の合計を見つける必要があります。

問題を理解するために例を見てみましょう

入力

N = 10

出力

18

説明

Maximum sum with LCM 10 is 1 + 2 + 5 + 10 = 18

ソリューションアプローチ

この問題の簡単な解決策は、数値NをLCMとして使用する場合、Nのすべての異なる除数を取得し、それらを合計してmaxSumを取得する必要があるという考えを使用することです。

このために、Nのすべての因子を見つけます。次に、それらを合計すると、LCMがNであることに寄与する可能性のあるすべての数値を考慮したため、これが最大になります。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;

int calcFactorSum(int N){
   int maxSum = 0;
   for (int i = 1; i*i <= N; i++){
      if (N % i == 0) {
         if (i == (N/i))
            maxSum = maxSum + i;
         else
            maxSum = maxSum + i + (N/i);
      }
   }
   return maxSum;
}
int main(){
   int N = 42;
   cout<<"The sum of distinct numbers with LCM as "<<N<<" is "<<calcFactorSum(N);
   return 0;
}

出力

The sum of distinct numbers with LCM as 42 is 96