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