Tìm tổng các thừa số lẻ của một số bằng C ++.

Trong phần này, chúng ta sẽ xem cách chúng ta có thể lấy tổng của tất cả các thừa số nguyên tố lẻ của một số một cách hiệu quả. Có một số nói n =1092, chúng ta phải lấy tất cả các thừa số của điều này. Các thừa số nguyên tố của 1092 là 2, 2, 3, 7, 13. Tổng của tất cả các thừa số lẻ là 3 + 7 + 13 =23. Để giải bài toán này, chúng ta phải tuân theo quy tắc này -

• Khi một số chia hết cho 2, hãy bỏ qua yếu tố đó và chia số đó nhiều lần cho 2.
• Bây giờ số phải là số lẻ. Bây giờ bắt đầu từ 3 đến căn bậc hai của một số, nếu số đó chia hết cho giá trị hiện tại, thì hãy cộng thừa số với tổng và đổi số bằng cách chia nó với số hiện tại rồi tiếp tục.
• Cuối cùng, số còn lại cũng sẽ được thêm vào nếu số còn lại là số lẻ

Hãy để chúng tôi xem thuật toán để hiểu rõ hơn.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

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