C ++を使用して、数値の奇数因子の合計を求めます。

このセクションでは、効率的な方法で、数値のすべての奇数の素因数の合計を取得する方法を説明します。 n =1092と言う数があります、これのすべての要因を取得する必要があります。 1092の素因数は2、2、3、7、13です。すべての奇数の因数の合計は3 + 7 + 13 =23です。この問題を解決するには、この規則に従う必要があります-

• 数値が2で割り切れる場合は、その係数を無視して、数値を2で繰り返し除算します。
• これで、数値は奇数になります。ここで、数値の3から平方根まで、数値が現在の値で割り切れる場合は、合計で係数を加算し、現在の数値で除算して数値を変更してから続行します。
• 最後に、残りの数が奇数の場合、残りの数も追加されます

より良いアイデアを得るためのアルゴリズムを見てみましょう。

アルゴリズム

printPrimeFactors(n):
begin
sum := 0
   while n is divisible by 2, do
      n := n / 2
   done
   for i := 3 to , increase i by 2, do
      while n is divisible by i, do
         sum := sum + i
         n := n / i
      done
   done
   if n > 2, then
      if n is odd, then
         sum := sum + n
      end if
   end if
end

例

#include<iostream>
#include<cmath>
using namespace std;
int sumOddFactors(int n){
   int i, sum = 0;
   while(n % 2 == 0){
      n = n/2; //reduce n by dividing this by 2
   }
   //as the number is not divisible by 2 anymore, all factors are odd
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
      while(n % i == 0){
         sum += i;
         n = n/i;
      }
   }
   if(n > 2){
      if(n%2 == 1)
      sum += n;
   }
   return sum;
}
main() {
   int n;
   cout << "Enter a number: ";
   cin >> n;
   cout <<"Sum of all odd prime factors: "<< sumOddFactors(n);
}

出力

Enter a number: 1092
Sum of all odd prime factors: 23