Minimizar el costo de dividir un número

Dado un número entero N ≥ 2 , puede dividir el número como una suma de k enteros, es decir , N = k1 + k2 + … + kn donde cada k-ésimo elemento es ≥ 2 , entonces el costo de dividir se calcula como maxDiv(k1) + maxDiv( k2) + … + maxDiv(kn) donde maxDiv(x) es el máximo divisor de x que es < x . 
La tarea es dividir el número de tal manera que el costo se minimice, imprimir el costo minimizado al final.

Ejemplos:

Entrada: N = 6 
Salida: 2 
6 se puede representar como (3 + 3) y el costo será 1 + 1 = 2.

Entrada: N = 5 
Salida: 1

Acercarse: 

• Cuando n es primo, entonces el costo será 1 ya que no tenemos que dividir n y el mayor divisor de n menor que él mismo será 1 .
• Si n es impar y n – 2 es primo, entonces n se puede dividir en (2 + primo), lo que costará 1 + 1 = 2 .
• Si n es par, entonces el costo será 2 como la conjetura de Goldbach , todo número par mayor que 2 se puede expresar como la suma de dos números primos, lo cual se demuestra por 4 * 10 ¹⁸ .
• Si no se cumplen todas las condiciones anteriores, entonces n debe ser impar ahora y si se resta 3 de n , se volverá par, lo que se puede expresar como (3 + par) = (3 + primo + primo) que costará 3 .

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// check if a number is prime or not
bool isPrime(int x)
{
    // run a loop upto square root of x
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0)
            return 0;
    }
    return 1;
}
 
// Function to return the minimized cost
int minimumCost(int n)
{
    // If n is prime
    if (isPrime(n))
        return 1;
 
    // If n is odd and can be
    // split into (prime + 2)
    // then cost will be 1 + 1 = 2
    if (n % 2 == 1 && isPrime(n - 2))
        return 2;
 
    // Every non-prime even number
    // can be expressed as the
    // sum of two primes
    if (n % 2 == 0)
        return 2;
 
    // n is odd so n can be split into (3 + even)
    // further even part can be
    // split into (prime + prime)
    // (3 + prime + prime) will cost 3
    return 3;
}
 
// Driver code
int main()
{
    int n = 6;
    cout << minimumCost(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// check if a number is prime or not
static boolean isPrime(int x)
{
    // run a loop upto square root of x
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}
 
// Function to return the minimized cost
static int minimumCost(int n)
{
    // If n is prime
    if (isPrime(n))
        return 1;
 
    // If n is odd and can be
    // split into (prime + 2)
    // then cost will be 1 + 1 = 2
    if (n % 2 == 1 && isPrime(n - 2))
        return 2;
 
    // Every non-prime even number
    // can be expressed as the
    // sum of two primes
    if (n % 2 == 0)
        return 2;
 
    // n is odd so n can be split into (3 + even)
    // further even part can be
    // split into (prime + prime)
    // (3 + prime + prime) will cost 3
    return 3;
}
 
// Driver code
public static void main(String args[])
{
    int n = 6;
    System.out.println(minimumCost(n));
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 implementation of the approach
from math import sqrt
 
# check if a number is prime or not
def isPrime(x) :
 
    # run a loop upto square root of x
    for i in range(2, int(sqrt(x)) + 1) :
        if (x % i == 0) :
            return 0;
             
    return 1;
 
# Function to return the minimized cost
def minimumCost(n) :
 
    # If n is prime
    if (isPrime(n)) :
        return 1;
 
    # If n is odd and can be
    # split into (prime + 2)
    # then cost will be 1 + 1 = 2
    if (n % 2 == 1 and isPrime(n - 2)) :
        return 2;
 
    # Every non-prime even number
    # can be expressed as the
    # sum of two primes
    if (n % 2 == 0) :
        return 2;
 
    # n is odd so n can be split into
    # (3 + even) further even part can be
    # split into (prime + prime)
    # (3 + prime + prime) will cost 3
    return 3;
 
# Driver code
if __name__ == "__main__" :
 
    n = 6;
    print(minimumCost(n));
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
public class GFG
{
  
// check if a number is prime or not
static bool isPrime(int x)
{
    // run a loop upto square root of x
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}
  
// Function to return the minimized cost
static int minimumCost(int n)
{
    // If n is prime
    if (isPrime(n))
        return 1;
  
    // If n is odd and can be
    // split into (prime + 2)
    // then cost will be 1 + 1 = 2
    if (n % 2 == 1 && isPrime(n - 2))
        return 2;
  
    // Every non-prime even number
    // can be expressed as the
    // sum of two primes
    if (n % 2 == 0)
        return 2;
  
    // n is odd so n can be split into (3 + even)
    // further even part can be
    // split into (prime + prime)
    // (3 + prime + prime) will cost 3
    return 3;
}
  
// Driver code
public static void Main(String []args)
{
    int n = 6;
    Console.WriteLine(minimumCost(n));
}
}
  
// This code is contributed by
// Rajput-Ji

<?php
// PHP implementation of the approach
// check if a number is prime or not
function isPrime($x)
{
    // run a loop upto square root of x
    for ($i = 2; $i * $i <= $x; $i++)
    {
        if ($x % $i == 0)
            return 0;
    }
    return 1;
}
 
// Function to return the minimized cost
function minimumCost($n)
{
    // If n is prime
    if (isPrime($n))
        return 1;
 
    // If n is odd and can be
    // split into (prime + 2)
    // then cost will be 1 + 1 = 2
    if ($n % 2 == 1 && isPrime($n - 2))
        return 2;
 
    // Every non-prime even number
    // can be expressed as the
    // sum of two primes
    if ($n % 2 == 0)
        return 2;
 
    // n is odd so n can be split into (3 + even)
    // further even part can be
    // split into (prime + prime)
    // (3 + prime + prime) will cost 3
    return 3;
}
 
// Driver code
$n = 6;
echo(minimumCost($n));
 
// This code is contributed by Code_Mech.

<script>
// Javascript implementation of the approach
// check if a number is prime or not
function isPrime(x)
{
    // run a loop upto square root of x
    for (let i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return 0;
    }
    return 1;
}
 
// Function to return the minimized cost
function minimumCost(n)
{
    // If n is prime
    if (isPrime(n))
        return 1;
 
    // If n is odd and can be
    // split into (prime + 2)
    // then cost will be 1 + 1 = 2
    if (n % 2 == 1 && isPrime(n - 2))
        return 2;
 
    // Every non-prime even number
    // can be expressed as the
    // sum of two primes
    if (n % 2 == 0)
        return 2;
 
    // n is odd so n can be split into (3 + even)
    // further even part can be
    // split into (prime + prime)
    // (3 + prime + prime) will cost 3
    return 3;
}
 
// Driver code
let n = 6;
document.write(minimumCost(n));
 
// This code is contributed by _saurabh_jaiswal.
 
</script>

2

Complejidad de tiempo: O(sqrt(n))
Espacio auxiliar: O(1)