Dividir n en números compuestos máximos

Dado n, imprime el número máximo de números compuestos que suman n. Los primeros números compuestos son 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ……… 
Ejemplos: 
 

Input: 90   
Output: 22
Explanation: If we add 21 4's, then we 
get 84 and then add 6 to it, we get 90.

Input: 10
Output: 2
Explanation: 4 + 6 = 10

A continuación se presentan algunas observaciones importantes. 
 

1. Si el número es menor que 4, no tendrá ninguna combinación.
2. Si el número es 5, 7, 11, no tendrá división.
3. Dado que el número compuesto más pequeño es 4, tiene sentido utilizar el número máximo de 4.
4. Para los números que no dejan un resto compuesto cuando se dividen por 4, hacemos lo siguiente. Si el resto es 1, le restamos 9 para obtener el número que es perfectamente divisible por 4. Si el resto es 2, entonces restamos 6 para hacer un número que es perfectamente divisible por 4. Si el resto es 3, entonces réstale 15 para hacer n perfectamente divisible por 4, y 15 se puede formar con 9 + 6.

Entonces, la observación principal es hacer n tal que se componga de un número máximo de 4 y el resto se pueda formar con 6 y 9. No necesitaremos números compuestos más que eso, ya que los números compuestos por encima de 9 se pueden formar de 4, 6 y 9.
A continuación se muestra la implementación del enfoque anterior 
 

// CPP program to split a number into maximum
// number of composite numbers.
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate the maximum number of
// composite numbers adding upto n
int count(int n)
{
    // 4 is the smallest composite number
    if (n < 4)
        return -1;
 
    // stores the remainder when n is divided
    // by 4
    int rem = n % 4;
 
    // if remainder is 0, then it is perfectly
    // divisible by 4.
    if (rem == 0)
        return n / 4;
 
    // if the remainder is 1
    if (rem == 1) {
 
        // If the number is less then 9, that
        // is 5, then it cannot be expressed as
        // 4 is the only composite number less
        // than 5
        if (n < 9)
            return -1;
 
        // If the number is greater then 8, and
        // has a remainder of 1, then express n
        // as n-9 a and it is perfectly divisible
        // by 4 and for 9, count 1.
        return (n - 9) / 4 + 1;
    }
 
     
    // When remainder is 2, just subtract 6 from n,
    // so that n is perfectly divisible by 4 and
    // count 1 for 6 which is subtracted.
    if (rem == 2)
        return (n - 6) / 4 + 1;
 
 
    // if the number is 7, 11 which cannot be
    // expressed as sum of any composite numbers
    if (rem == 3) {
        if (n < 15)
            return -1;
 
        // when the remainder is 3, then subtract
        // 15 from it and n becomes perfectly
        // divisible by 4 and we add 2 for 9 and 6,
        // which is getting subtracted to make n
        // perfectly divisible by 4.
        return (n - 15) / 4 + 2;
    }
}
 
// driver program to test the above function
int main()
{
    int n = 90;
    cout << count(n) << endl;
 
    n = 143;
    cout << count(n) << endl;
    return 0;
}

// Java program to split a number into maximum
// number of composite numbers.
import java.io.*;
 
class GFG
{
    // function to calculate the maximum number of
    // composite numbers adding upto n
    static int count(int n)
    {
        // 4 is the smallest composite number
        if (n < 4)
            return -1;
     
        // stores the remainder when n is divided
        // by 4
        int rem = n % 4;
     
        // if remainder is 0, then it is perfectly
        // divisible by 4.
        if (rem == 0)
            return n / 4;
     
        // if the remainder is 1
        if (rem == 1) {
     
            // If the number is less then 9, that
            // is 5, then it cannot be expressed as
            // 4 is the only composite number less
            // than 5
            if (n < 9)
                return -1;
     
            // If the number is greater then 8, and
            // has a remainder of 1, then express n
            // as n-9 a and it is perfectly divisible
            // by 4 and for 9, count 1.
            return (n - 9) / 4 + 1;
        }
     
         
        // When remainder is 2, just subtract 6 from n,
        // so that n is perfectly divisible by 4 and
        // count 1 for 6 which is subtracted.
        if (rem == 2)
            return (n - 6) / 4 + 1;
     
     
        // if the number is 7, 11 which cannot be
        // expressed as sum of any composite numbers
        if (rem == 3)
        {
            if (n < 15)
                return -1;
     
            // when the remainder is 3, then subtract
            // 15 from it and n becomes perfectly
            // divisible by 4 and we add 2 for 9 and 6,
            // which is getting subtracted to make n
            // perfectly divisible by 4.
            return (n - 15) / 4 + 2;
        }
        return 0;
    }
     
    // Driver program
    public static void main (String[] args)
    {
        int n = 90;
        System.out.println(count(n));
 
        n = 143;
        System.out.println(count(n));
    }
}
 
// This code is contributed by vt_m.

# Python3 program to split a number into
# maximum number of composite numbers.
 
# Function to calculate the maximum number
# of composite numbers adding upto n
def count(n):
 
    # 4 is the smallest composite number
    if (n < 4):
        return -1
 
    # stores the remainder when n 
    # is divided n is divided by 4
    rem = n % 4
 
    # if remainder is 0, then it is 
    # perfectly divisible by 4.
    if (rem == 0):
        return n // 4
 
    # if the remainder is 1
    if (rem == 1):
 
        # If the number is less then 9, that
        # is 5, then it cannot be expressed as
        # 4 is the only composite number less
        # than 5
        if (n < 9):
            return -1
 
        # If the number is greater then 8, and
        # has a remainder of 1, then express n
        # as n-9 a and it is perfectly divisible
        # by 4 and for 9, count 1.
        return (n - 9) // 4 + 1
     
 
     
    # When remainder is 2, just subtract 6 from n,
    # so that n is perfectly divisible by 4 and
    # count 1 for 6 which is subtracted.
    if (rem == 2):
        return (n - 6) // 4 + 1
 
 
    # if the number is 7, 11 which cannot be
    # expressed as sum of any composite numbers
    if (rem == 3):
        if (n < 15):
            return -1
 
        # when the remainder is 3, then subtract
        # 15 from it and n becomes perfectly
        # divisible by 4 and we add 2 for 9 and 6,
        # which is getting subtracted to make n
        # perfectly divisible by 4.
        return (n - 15) // 4 + 2
 
# Driver Code
n = 90
print(count(n))
 
n = 143
print(count(n))
 
# This code is contributed by Anant Agarwal.

// C# program to split a number into maximum
// number of composite numbers.
using System;
 
class GFG {
     
    // function to calculate the maximum number
    // of composite numbers adding upto n
    static int count(int n)
    {
         
        // 4 is the smallest composite number
        if (n < 4)
            return -1;
      
        // stores the remainder when n is divided
        // by 4
        int rem = n % 4;
      
        // if remainder is 0, then it is perfectly
        // divisible by 4.
        if (rem == 0)
            return n / 4;
      
        // if the remainder is 1
        if (rem == 1) {
      
            // If the number is less then 9, that
            // is 5, then it cannot be expressed as
            // 4 is the only composite number less
            // than 5
            if (n < 9)
                return -1;
      
            // If the number is greater then 8, and
            // has a remainder of 1, then express n
            // as n-9 a and it is perfectly divisible
            // by 4 and for 9, count 1.
            return (n - 9) / 4 + 1;
        }
      
          
        // When remainder is 2, just subtract 6 from n,
        // so that n is perfectly divisible by 4 and
        // count 1 for 6 which is subtracted.
        if (rem == 2)
            return (n - 6) / 4 + 1;
      
      
        // if the number is 7, 11 which cannot be
        // expressed as sum of any composite numbers
        if (rem == 3)
        {
            if (n < 15)
                return -1;
      
            // when the remainder is 3, then subtract
            // 15 from it and n becomes perfectly
            // divisible by 4 and we add 2 for 9 and 6,
            // which is getting subtracted to make n
            // perfectly divisible by 4.
            return (n - 15) / 4 + 2;
        }
         
        return 0;
    }
      
    // Driver program
    public static void Main()
    {
        int n = 90;
        Console.WriteLine(count(n));
  
        n = 143;
        Console.WriteLine(count(n));
    }
}
  
// This code is contributed by Anant Agarwal.

<?php
// PHP program to split a number
// into maximum number of
// composite numbers.
 
// function to calculate the
// maximum number of composite
// numbers adding upto n
function c_ount($n)
{
     
    // 4 is the smallest
    // composite number
    if ($n < 4)
        return -1;
 
    // stores the remainder when
    // n is divided by 4
    $rem = $n % 4;
 
    // if remainder is 0, then it
    // is perfectly divisible by 4.
    if ($rem == 0)
        return $n / 4;
 
    // if the remainder is 1
    if ($rem == 1) {
 
        // If the number is less
        // then 9, that is 5, then
        // it cannot be expressed
        // as  4 is the only
        //composite number less
        // than 5
        if ($n < 9)
            return -1;
 
        // If the number is greater
        // then 8, and has a
        // remainder of 1, then
        // express n as n-9 a and
        // it is perfectly divisible
        // by 4 and for 9, count 1.
        return ($n - 9) / 4 + 1;
    }
 
     
    // When remainder is 2, just
    // subtract 6 from n, so that n
    // is perfectly divisible by 4
    // and count 1 for 6 which is
    // subtracted.
    if ($rem == 2)
        return ($n - 6) / 4 + 1;
 
 
    // if the number is 7, 11 which
    // cannot be expressed as sum of
    // any composite numbers
    if ($rem == 3) {
        if ($n < 15)
            return -1;
 
        // when the remainder is 3,
        // then subtract 15 from it
        // and n becomes perfectly
        // divisible by 4 and we add
        // 2 for 9 and 6, which is
        // getting subtracted to make
        // n perfectly divisible by 4.
        return ($n - 15) / 4 + 2;
    }
}
 
// driver program to test the above
// function
 
    $n = 90;
    echo c_ount($n),"\n";
 
    $n = 143;
    echo c_ount($n);
 
// This code is contributed by anuj_67.
?>

<script>
    // Javascript program to split a number
// into maximum number of
// composite numbers.
   
// function to calculate the
// maximum number of composite
// numbers adding upto n
function c_ount(n)
{
       
    // 4 is the smallest
    // composite number
    if (n < 4)
        return -1;
   
    // stores the remainder when
    // n is divided by 4
    let rem = n % 4;
   
    // if remainder is 0, then it
    // is perfectly divisible by 4.
    if (rem == 0)
        return n / 4;
   
    // if the remainder is 1
    if (rem == 1) {
   
        // If the number is less
        // then 9, that is 5, then
        // it cannot be expressed
        // as  4 is the only
        //composite number less
        // than 5
        if (n < 9)
            return -1;
   
        // If the number is greater
        // then 8, and has a
        // remainder of 1, then
        // express n as n-9 a and
        // it is perfectly divisible
        // by 4 and for 9, count 1.
        return (n - 9) / 4 + 1;
    }
   
       
    // When remainder is 2, just
    // subtract 6 from n, so that n
    // is perfectly divisible by 4
    // and count 1 for 6 which is
    // subtracted.
    if (rem == 2)
        return (n - 6) / 4 + 1;
   
   
    // if the number is 7, 11 which
    // cannot be expressed as sum of
    // any composite numbers
    if (rem == 3) {
        if (n < 15)
            return -1;
   
        // when the remainder is 3,
        // then subtract 15 from it
        // and n becomes perfectly
        // divisible by 4 and we add
        // 2 for 9 and 6, which is
        // getting subtracted to make
        // n perfectly divisible by 4.
        return (n - 15) / 4 + 2;
    }
}
   
// driver program to test the above
// function
   
    let n = 90;
    document.write(c_ount(n) + "<br>");
   
    n = 143;
    document.write(c_ount(n));
   
// This code is contributed by _saurabh_jaiswal.
</script>

Producción: 
 

22 
34 

Complejidad temporal: O(1) 
Espacio auxiliar: O(1) 
Este artículo es una contribución de Raja Vikramaditya . 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.