Dividir un número tal que la suma de los máximos divisores de todas las partes sea mínima

Necesitamos dividir un número n tal que la suma de los máximos divisores de todas las partes sea mínima. 

Ejemplos: 

Input:  n = 27
Output: Minimum sum of maximum
        divisors of parts = 3
Explanation : We can split 27 as 
follows: 27 =  13 + 11 + 3,
Maximum divisor of 13 = 1,
                   11 = 1,
                   3 = 1.
Answer = 3 (1 + 1 + 1).

Input : n = 4
Output: Minimum sum of maximum
        divisors of parts = 2
Explanation : We can write 4 = 2 + 2
Maximum divisor of 2 = 1,
So answer is 1 + 1 = 2.

Necesitamos minimizar los divisores máximos. Es obvio que si N es primo, máximo divisor = 1. Si el número no es primo, entonces el número debe ser al menos 2. 

Según la conjetura de Goldbach , todo número par se puede expresar como la suma de dos números primos. Para nuestro problema habrá dos casos: 

1) Cuando el número es par, se puede expresar como la suma de dos números primos y nuestra respuesta será 2 porque el máximo divisor de un número primo es 1. 
2) Cuando el número es impar, también se puede escribir como suma de números primos, n = 2 + (n-2); si (n-2) es un número primo (respuesta = 2), de lo contrario. Consulte el número impar como suma de números primos para obtener más detalles. 
n = 3 + (n-3); (n-3) es un número par y es la suma de dos números primos (respuesta = 3). 

A continuación se muestra la implementación de este enfoque.  

// CPP program to break a number such
// that sum of maximum divisors of all
// parts is minimum
#include <iostream>
using namespace std;
 
// Function to check if a number is
// prime or not.
bool isPrime(int n)
{
    int i = 2;
    while (i * i <= n) {
        if (n % i == 0)
            return false;
        i++;
    }
    return true;
}
 
int minimumSum(int n)
{
    if (isPrime(n))
        return 1;
 
    // If n is an even number (we can
    // write it as sum of two primes)
    if (n % 2 == 0)
        return 2;
 
    // If n is odd and n-2 is prime.
    if (isPrime(n - 2))
        return 2;
 
    // If n is odd, n-3 must be even.
    return 3;
}
 
// Driver code
int main()
{
    int n = 27;
    cout << minimumSum(n);
    return 0;
}

// JAVA Code for Break a number such that sum
// of maximum divisors of all parts is minimum
import java.util.*;
 
class GFG {
 
    // Function to check if a number is
    // prime or not.
    static boolean isPrime(int n)
    {
        int i = 2;
 
        while (i * i <= n) {
            if (n % i == 0)
                return false;
            i++;
        }
        return true;
    }
 
    static int minimumSum(int n)
    {
        if (isPrime(n))
            return 1;
 
        // If n is an even number (we can
        // write it as sum of two primes)
        if (n % 2 == 0)
            return 2;
 
        // If n is odd and n-2 is prime.
        if (isPrime(n - 2))
            return 2;
 
        // If n is odd, n-3 must be even.
        return 3;
    }
 
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int n = 4;
        System.out.println(minimumSum(n));
    }
}
 
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to break a number
# such that sum of maximum divisors
# of all parts is minimum
 
# Function to check if a number is
# prime or not.
def isPrime( n):
    i = 2
     
    while (i * i <= n):
         
        if (n % i == 0):
            return False
        i+= 1
 
    return True
     
def minimumSum( n):
     
    if (isPrime(n)):
        return 1
     
    # If n is an even number (we can
    # write it as sum of two primes)
    if (n % 2 == 0):
        return 2
     
    # If n is odd and n-2 is prime.
    if (isPrime(n - 2)):
        return 2
         
    # If n is odd, n-3 must be even.
    return 3
 
# Driver code
n = 27
print(minimumSum(n))
 
# This code is contributed by "Abhishek Sharma 44"

// C# Code for Break a number
// such that sum of maximum
// divisors of all parts is minimum
using System;
 
class GFG {
 
    // Function to check if a number is
    // prime or not.
    static bool isPrime(int n)
    {
        int i = 2;
 
        while (i * i <= n) {
            if (n % i == 0)
                return false;
            i++;
        }
        return true;
    }
 
    static int minimumSum(int n)
    {
        if (isPrime(n))
            return 1;
 
        // If n is an even number (we can
        // write it as sum of two primes)
        if (n % 2 == 0)
            return 2;
 
        // If n is odd and n-2 is prime.
        if (isPrime(n - 2))
            return 2;
 
        // If n is odd, n-3 must be even.
        return 3;
    }
 
    // Driver program
    public static void Main()
    {
        int n = 27;
        Console.WriteLine(minimumSum(n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to break a number
// such that sum of maximum
// divisors of all parts is minimum
 
// Function to check if a
// number is prime or not.
function isPrime($n)
{
    $i = 2;
    while ($i * $i <= $n)
    {
        if ($n % $i == 0)
            return false;
        $i++;
    }
    return true;
}
 
function minimumSum($n)
{
    if (isPrime($n))    
        return 1;
 
    // If n is an even
    // number (we can
    // write it as sum
    // of two primes)
    if ($n % 2 == 0)
        return 2;
 
    // If n is odd and
    // n - 2 is prime.
    if (isPrime($n - 2))
        return 2;
 
    // If n is odd,
    // n - 3 must be even.
    return 3;
}
 
// Driver code
$n = 27;
echo minimumSum($n);
 
// This code is contributed by aj_36
?>

<script>
 
// JavaScript program to break a number
// such that sum of maximum divisors of
// all parts is minimum
 
// Function to check if a number is
// prime or not.
function isPrime(n)
{
    let i = 2;
     
    while (i * i <= n)
    {
        if (n % i == 0)
            return false;
             
        i++;
    }
    return true;
}
 
function minimumSum(n)
{
    if (isPrime(n))
        return 1;
 
    // If n is an even number (we can
    // write it as sum of two primes)
    if (n % 2 == 0)
        return 2;
 
    // If n is odd and n-2 is prime.
    if (isPrime(n - 2))
        return 2;
 
    // If n is odd, n-3 must be even.
    return 3;
}
 
// Driver code
let n = 27;
 
document.write(minimumSum(n));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción : 

    3

Complejidad temporal: O(√n) 
Espacio auxiliar: O(1)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.