Encuentra la suma mínima de los factores de un número

Dado un número, hallar la suma mínima de sus factores.
Ejemplos: 
 

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 7

Input : 105
Output : 15

Para minimizar la suma, debemos factorizar los factores tanto como sea posible. Con este proceso, tenemos factores primos . Entonces, para encontrar la suma mínima del producto del número, encontramos la suma de los factores primos del producto.
 

// CPP program to find minimum
// sum of product of number
#include <bits/stdc++.h>
using namespace std;
 
// To find minimum sum of
// product of number
int findMinSum(int num)
{
    int sum = 0;
 
    // Find factors of 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 sum of numbers
    // having minimum product
    return sum;
}
 
// Driver program to test above function
int main()
{
    int num = 12;
 
    cout << findMinSum(num);
 
    return 0;
}

// Java program to find minimum
// sum of product of number
 
public class Main {
 
    // To find minimum sum of
    // product of number
    static int findMinSum(int num)
    {
        int sum = 0;
 
        // Find factors of 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 sum of numbers
        // having minimum product
        return sum;
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
        int num = 12;
        System.out.println(findMinSum(num));
    }
}

# Python program to find minimum
# sum of product of number
  
# To find minimum sum of
# product of number
def findMinSum(num):
    sum = 0
     
    # Find factors of number
    # and add to the sum
    i = 2
    while(i * i <= num):
        while(num % i == 0):
            sum += i
            num //= i
        i += 1
    sum += num
     
    # Return sum of numbers
    # having minimum product
    return sum
 
# Driver Code
num = 12
print (findMinSum(num))
 
# This code is contributed by Sachin Bisht

// C# program to find minimum
// sum of product of number
using System;
 
public class GFG {
 
    // To find minimum sum of
    // product of number
    static int findMinSum(int num)
    {
        int sum = 0;
 
        // Find factors of 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 sum of numbers
        // having minimum product
        return sum;
    }
 
    // Driver Code
    public static void Main()
    {
        int num = 12;
        Console.Write(findMinSum(num));
    }
     
}
 
// This Code is contributed by Nitin Mittal.

<?php
// PHP program to find minimum
// sum of product of number
 
// To find minimum sum of
// product of number
function findMinSum($num)
{
    $sum = 0;
 
    // Find factors of number
    // and add to the sum
    for ($i = 2; $i * $i <= $num; $i++)
    {
        while ($num % $i == 0)
        {
            $sum += $i;
            $num /= $i;
        }
    }
    $sum += $num;
 
    // Return sum of numbers
    // having minimum product
    return $sum;
}
 
// Driver Code
$num = 12;
 
echo(findMinSum($num));
 
// This code is contributed by Ajit.
?>

<script>
 
// Javascript program to find minimum
// sum of product of number
   
// To find minimum sum of
// product of number
function findMinSum(num)
{
    let sum = 0;
   
    // Find factors of number
    // and add to the sum
    for (let i = 2; i * i <= num; i++) 
    {
        while (num % i == 0) 
        {
            sum += i;
            num /= i;
        }
    }
    sum += num;
   
    // Return sum of numbers
    // having minimum product
    return sum;
}
   
// Driver Code
let num = 12;
   
document.write(findMinSum(num));
   
// This code is contributed by _saurabh_jaiswal.
 
</script>

Producción: 

7

Complejidad de tiempo: O (n ^1/2 * log n)

Espacio auxiliar: O(1)
Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.