C Program for Find sum of odd factors of a number
Write a C program for a given number n, the task is to find the odd factor sum.
Examples:
Input : n = 30
Output : 24
Explanation: Odd dividers sum 1 + 3 + 5 + 15 = 24Input : 18
Output : 13
Explanation: Odd dividers sum 1 + 3 + 9 = 13
C Program for Find sum of odd factors of a number using Prime Factorization:
To find sum of odd factors, we simply need to ignore even factors and their powers. For example, consider n = 18. It can be written as 2132 and sum of all factors is (1)*(1 + 2)*(1 + 3 + 32). Sum of odd factors (1)*(1+3+32) = 13.
To remove all even factors, we repeatedly divide n while it is divisible by 2. After this step, we only get odd factors. Note that 2 is the only even prime.
Let p1, p2, … pk be prime factors of n. Let a1, a2, .. ak be highest powers of p1, p2, .. pk respectively that divide n, i.e., we can write n as n = (p1a1)*(p2a2)* … (pkak).
Sum of divisors = (1 + p1 + p12 ... p1a1) * (1 + p2 + p22 ... p2a2) * ............................................. (1 + pk + pk2 ... pkak)
Below is the Implementation of the above approach:
C
#include <math.h> #include <stdio.h> // Function to calculate the sum of all factors of 'n' int sumofoddFactors( int n) { // Initialize the result to 1 int res = 1; // Ignore even factors by removing all powers of 2 while (n % 2 == 0) n = n / 2; for ( int i = 3; i * i <= n; i++) { // Initialize a count for the current prime factor int count = 0; // Initialize the current sum for the prime factor int curr_sum = 1; // Initialize the current term for the prime factor int curr_term = 1; while (n % i == 0) { // Increment the count for this prime factor count++; // Remove the factor from 'n' n = n / i; // Update the current term curr_term *= i; // Add the current term to the current sum curr_sum += curr_term; } // Multiply the result by the current sum res *= curr_sum; } // This condition is to handle the case when 'n' is a // prime number. if (n >= 2) res *= (1 + n); // Return the final result return res; } int main() { // The input number 'n' int n = 30; // Calculate and print the sum of odd factors printf ( "%d\n" , sumofoddFactors(n)); // Return 0 to indicate successful execution return 0; } |
24
Time Complexity: O(n1/2)
Auxiliary Space: O(1)
Please refer complete article on Find sum of odd factors of a number for more details!