Operaciones de conteo del tipo dado requeridas para reducir N a 0

Dado un entero n . La tarea es contar el número de operaciones requeridas para reducir n a 0 . En cada operación, n se puede actualizar como n = n – d donde d es el divisor primo más pequeño de n .
Ejemplos: 
 

Entrada: n = 5 
Salida: 1 
5 es el divisor primo más pequeño, por lo que se resta y n se reduce a 0.
Entrada: n = 25 
Salida: 11 
5 es el divisor primo más pequeño, por lo que se resta y n se reduce a 20. Entonces 2 es el divisor más pequeño y así sucesivamente.
Entrada: n = 4 
Salida: 2 
 

Acercarse: 
 

1. Cuando n es par , el divisor primo más pequeño de n será 2 y restar 2 de n nuevamente dará un número entero par, es decir , se elegirá la ganancia 2 como el divisor primo más pequeño y estos pasos se repetirán hasta que n se reduzca a 0 .
2. Cuando n es impar , entonces el divisor primo más pequeño de n también será impar y restar un entero impar de otro entero impar dará como resultado un entero par y luego se puede averiguar el resultado repitiendo el paso 1 para el entero par actual.
3. Por lo tanto, la tarea es encontrar el divisor más pequeño d , restarlo, n = n – d e imprimir 1 + ((n – d) / 2) . 
    

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

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the required
// number of operations
int countOperations (int n)
{
    int i = 2;
     
    // Finding the smallest divisor
    while ((i * i) < n && (n % i))
        i += 1;
     
    if ((i * i) > n)
        i = n;
     
    // Return the count of operations
    return (1 + (n - i)/2);
}
 
// Driver code
int main()
{
    int n = 5;
    cout << countOperations(n);
}
 
//This code is contributed by Shivi_Aggarwal

// Java implementation of the approach
class GFG
{
 
// Function to return the required
// number of operations
static int countOperations (int n)
{
    int i = 2;
     
    // Finding the smallest divisor
    while ((i * i) < n && (n % i) > 0)
        i += 1;
     
    if ((i * i) > n)
        i = n;
     
    // Return the count of operations
    return (1 + (n - i) / 2);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5;
    System.out.println(countOperations(n));
}
}
 
// This code is contributed
// by Akanksha Rai

# Python3 implementation of the approach
 
# Function to return the required
# number of operations
def countOperations(n):
    i = 2
     
    # Finding the smallest divisor
    while ((i * i) < n and (n % i)):
        i += 1
     
    if ((i * i) > n):
        i = n
     
    # Return the count of operations
    return (1 + (n - i)//2)
 
# Driver code
n = 5
print(countOperations(n))

// C# implementation of the approach
using System;
class GFG
{
 
// Function to return the required
// number of operations
static int countOperations (int n)
{
    int i = 2;
     
    // Finding the smallest divisor
    while ((i * i) < n && (n % i) > 0)
        i += 1;
     
    if ((i * i) > n)
        i = n;
     
    // Return the count of operations
    return (1 + (n - i) / 2);
}
 
// Driver code
static void Main()
{
    int n = 5;
    Console.WriteLine(countOperations(n));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function to return the required
// number of operations
function countOperations($n)
{
    $i = 2;
     
    # Finding the smallest divisor
    while (($i * $i) < $n and ($n % $i))
        $i += 1;
         
    if (($i * $i) > $n)
        $i = $n;
     
    # Return the count of operations
    return 1 + floor(($n - $i) / 2);
}
 
// Driver code
$n = 5 ;
echo countOperations($n);
 
// This code is contributed by Ryuga
?>

<script>
 
// JavaScript implementation of the approach
 
// Function to return the required
// number of operations
function countOperations (n)
{
    var i = 2;
     
    // Finding the smallest divisor
    while ((i * i) < n && (n % i))
        i += 1;
     
    if ((i * i) > n)
        i = n;
     
    // Return the count of operations
    return (1 + (n - i)/2);
}
 
// Driver code
var n = 5;
document.write( countOperations(n))
 
</script>

1

Complejidad del tiempo: 

Espacio Auxiliar: O(1)