C Program to Find minimum sum of factors of number
Write a C program for a given number N, the task is to find the minimum sum of its factors.
Examples:
Input : 12
Output : 7
Explanation:Following are different ways to factorize 12 and
sum of factors in different ways.
12 = 12 * 1 = 12 + 1 = 13
12 = 2 * 6 = 2 + 6 = 8
12 = 3 * 4 = 3 + 4 = 7
12 = 2 * 2 * 3 = 2 + 2 + 3 = 7
Therefore minimum sum is 7Input: 105
Output: 15
Approach:
To minimize sum, we must factorize factors as long as possible. With this process, we prime factors. So to find minimum sum of product of number, we find sum of prime factors of product.
Below is the implementation of the above approach:
C
// C program for the above approach #include <stdio.h> // To find the minimum sum of the product of numbers int findMinSum( int num) { int sum = 0; // Find factors of the number and add to the sum for ( int i = 2; i * i <= num; i++) { while (num % i == 0) { sum += i; num /= i; } } sum += num; // Return the sum of numbers having the minimum product return sum; } // Drivers Code int main() { int num = 12; printf ( "%d\n" , findMinSum(num)); return 0; } |
Output
7
Time Complexity : O(n1/2 * log n)
Auxiliary Space: O(1)
Please refer complete article on
for more details!