C Program for Find sum of odd factors of a number?

In this section, we will see how we can get the sum of all odd prime factors of a number in an efficient way. There is a number say n = 1092, we have to get all factor of this. The prime factors of 1092 are 2, 2, 3, 7, 13. The sum of all odd factors is 3+7+13 = 23. To solve this problem, we have to follow this rule −

• When the number is divisible by 2, ignore that factor, and divide the number by 2 repeatedly.

• Now the number must be odd. Now starting from 3 to square root of the number, if the number is divisible by current value, then add the factor with the sum, and change the number by divide it with the current number then continue.

• Finally, the remaining number will also be added if the remaining number is odd

Let us see the algorithm to get a better idea.

Algorithm

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

Example

#include<stdio.h> #include<math.h> 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;    printf("Enter a number: ");    scanf("%d", &n);    printf("Sum of all odd prime factors: %d", sumOddFactors(n)); }

Output

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