Minimice las operaciones para reducir N a 0 reemplazando N por su divisor en cada paso

Dado un entero positivo N . Encuentre el número mínimo de operaciones necesarias para reducir N a 0 cuando N puede reducirse por su divisor en cada operación.

Ejemplo:

Entrada: N = 5
Salida: 4
Explicación: 
Reducir 5 como 5-1=4.
Reduce 4 como 4-2=2.
Reduzca 2 como 2-1=1.
Reducir 1 como 1-1=0.

Entrada: N = 8
Salida: 4
Explicación:
Reducir 8 como 8-4=4.
Reduce 4 como 4-2=2.
Reduzca 2 como 2-1=1.
Reducir 1 como 1-1=0.

Enfoque ingenuo:

Un enfoque fácil es encontrar el divisor más alto de N cada vez hasta que N se convierta en 0.

Siga los pasos a continuación para resolver este problema:

• Atraviese hasta que N se convierta en 0 .
•  Encuentre el divisor más alto de N y reste de N .
• Cuente el número de iteraciones requeridas para que N se convierta en 0 de esta manera.
•  Devuelva el recuento calculado anteriormente como la respuesta final.

// C++ program to minimize operations
// to reduce N to 0 by replacing
// N by its divisor at each step
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll findElement(ll N)
{
    for (ll i = 2; i * i <= N; i++) {
        if (N % i == 0)
            return N / i;
    }
    return 1;
}
 
// Function to count minimum number
// of operation
ll minOperations(ll N)
{
    if (N < 0)
        return -1;
 
    ll count = 0;
    while (N) {
        ll divisor = findElement(N);
        N -= divisor;
        count++;
    }
    return count;
}
 
// Driver code
int main()
{
    ll N = 5;
    cout << minOperations(N);
 
    return 0;
}

// Java program to minimize operations
// to reduce N to 0 by replacing
// N by its divisor at each step
import java.io.*;
 
class GFG {
 
  static long findElement(long N)
  {
    for (long i = 2; i * i <= N; i++) {
      if (N % i == 0)
        return N / i;
    }
    return 1;
  }
 
  // Function to count minimum number
  // of operation
  static long minOperations(long N)
  {
    if (N < 0)
      return -1;
 
    long count = 0;
    while (N > 0) {
      long divisor = findElement(N);
      N -= divisor;
      count++;
    }
    return count;
  }
 
  // Driver code
  public static void main (String[] args) {
    long N = 5;
    System.out.print(minOperations(N));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 program to minimize operations
# to reduce N to 0 by replacing N by its
# divisor at each step
 
# function to find the element
def findElement(N):
    i = 2
    while i * i <= N:
        if N % i == 0:
            return int(N / i)
        i += 1
    return 1
 
# function to count the min number of operations
def minOperations(N):
    if N < 0:
        return -1
    count = 0
    while N:
        divisor = findElement(N)
        N -= divisor
        count += 1
    return count
 
# Driver Code
N = 5
print(minOperations(N))
 
# This code is contributed by phasing17

// C# program to minimize operations
// to reduce N to 0 by replacing
// N by its divisor at each step
using System;
class GFG {
  static long findElement(long N)
  {
    for (long i = 2; i * i <= N; i++) {
      if (N % i == 0)
        return N / i;
    }
    return 1;
  }
 
  // Function to count minimum number
  // of operation
  static long minOperations(long N)
  {
    if (N < 0)
      return -1;
 
    long count = 0;
    while (N > 0) {
      long divisor = findElement(N);
      N -= divisor;
      count++;
    }
    return count;
  }
 
  // Driver code
  public static void Main()
  {
    long N = 5;
    Console.WriteLine(minOperations(N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program to minimize operations
    // to reduce N to 0 by replacing
    // N by its divisor at each step
    const findElement = (N) => {
        for (let i = 2; i * i <= N; i++) {
            if (N % i == 0)
                return parseInt(N / i);
        }
        return 1;
    }
 
    // Function to count minimum number
    // of operation
    const minOperations = (N) => {
        if (N < 0)
            return -1;
 
        let count = 0;
        while (N) {
            let divisor = findElement(N);
            N -= divisor;
            count++;
        }
        return count;
    }
 
    // Driver code
    let N = 5;
    document.write(minOperations(N));
 
// This code is contributed by rakeshsahni
 
</script>

4

Complejidad de tiempo: O(N^(3/2))
Espacio auxiliar: O(1)

Enfoque eficiente: la solución anterior se puede optimizar mediante el cálculo previo utilizando el Tamiz de Eratóstenes para el factor primo más pequeño y modificándolo un poco para almacenar el factor más alto de N.

Siga los pasos a continuación para resolver este problema: 

• Calcule previamente el tamiz usando el tamiz de Eratóstenes para el factor primo mínimo de números hasta N
• Modifique el tamiz anterior almacenando 1 para todos los valores cero ; de lo contrario, i/sieve[i] para cada i-ésimo valor
• Atraviese hasta que N se convierta en 0 .
• Reste sieve[N] para cada iteración de N .
• Cuente el número de iteraciones requeridas para que N se convierta en 0 de esta manera.
• Devuelva el recuento calculado anteriormente como la respuesta final.

// C++ program to minimize operations
// to reduce N to 0 by replacing
// N by its divisor at each step
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 10000001
ll sieve[MAX];
 
// Function to calculate sieve
void makeSieve()
{
    ll i, j;
    sieve[0] = 0;
    sieve[1] = 1;
 
    for (i = 2; i < MAX; i++)
        sieve[i] = 0;
 
    for (i = 2; i * i <= MAX; i++) {
        if (!sieve[i]) {
            sieve[i] = i;
            for (j = i * i; j < MAX; j += i)
                if (!sieve[j])
                    sieve[j] = i;
        }
    }
    for (i = 2; i < MAX; i++) {
        if (!sieve[i])
            sieve[i] = 1;
        else
            sieve[i] = i / sieve[i];
    }
}
 
// Function to count minimum operations
ll minOperations(ll& N)
{
    if (N < 0)
        return -1;
 
    ll count = 0;
    makeSieve();
    while (N) {
        N -= sieve[N];
        count++;
    }
    return count;
}
 
// Driver Code
int main()
{
    ll N = 8;
    cout << minOperations(N);
 
    return 0;
}

// JAVA code to implement the above approach
import java.util.*;
class GFG {
 
  static int MAX= 10000001;
  static int[] sieve = new int[MAX];
 
  // Function to calculate sieve
  static void makeSieve()
  {
    int i, j;
    sieve[0] = 0;
    sieve[1] = 1;
 
    for (i = 2; i < MAX; i++)
      sieve[i] = 0;
 
    for (i = 2; i * i <= MAX; i++) {
      if (sieve[i]==0) {
        sieve[i] = i;
        for (j = i * i; j < MAX; j += i)
          if (sieve[j]==0)
            sieve[j] = i;
      }
    }
    for (i = 2; i < MAX; i++) {
      if (sieve[i]==0)
        sieve[i] = 1;
      else
        sieve[i] = i / sieve[i];
    }
  }
 
  // Function to count minimum operations
  static int minOperations(int N)
  {
    if (N < 0)
      return -1;
 
    int count = 0;
    makeSieve();
    while (N != 0) {
      N -= sieve[N];
      count++;
    }
    return count;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 8;
    System.out.print(minOperations(N));
  }
}
 
// This code is contributed by sanjoy_62.

# Python3 code to implement the above approach
 
MAX = 10000001
 
 
def makeSieve():
    sieve = [0] * MAX
    sieve[1] = 1
    for i in range(2, 1 + int(MAX ** 0.5)):
        if not sieve[i]:
            sieve[i] = i
            for j in range(i ** 2, MAX):
                if not sieve[j]:
                    sieve[j] = i
    for i in range(2, MAX):
        if not sieve[i]:
            sieve[i] = 1
        else:
            sieve[i] = (i // sieve[i])
    return sieve
 
 
def minOperations(N):
    if N < 0:
        return -1
    count = 0
    sieve = makeSieve()
    while N > 0:
        N -= (sieve[N])
        count += 1
    return count
 
 
# Driver Code
N = 8
print(minOperations(N))

// C# implementation of above approach
using System;
 
class GFG{
 
  static int MAX= 10000001;
  static int[] sieve = new int[MAX];
 
  // Function to calculate sieve
  static void makeSieve()
  {
    int i, j;
    sieve[0] = 0;
    sieve[1] = 1;
 
    for (i = 2; i < MAX; i++)
      sieve[i] = 0;
 
    for (i = 2; i * i <= MAX; i++) {
      if (sieve[i]==0) {
        sieve[i] = i;
        for (j = i * i; j < MAX; j += i)
          if (sieve[j]==0)
            sieve[j] = i;
      }
    }
    for (i = 2; i < MAX; i++) {
      if (sieve[i]==0)
        sieve[i] = 1;
      else
        sieve[i] = i / sieve[i];
    }
  }
 
  // Function to count minimum operations
  static int minOperations(int N)
  {
    if (N < 0)
      return -1;
 
    int count = 0;
    makeSieve();
    while (N != 0) {
      N -= sieve[N];
      count++;
    }
    return count;
  }
 
  // Driver Code
  static public void Main (){
 
    int N = 8;
    Console.Write(minOperations(N));
  }
}
 
// This code is contributed by code_hunt.

<script>
// JavaScript program to minimize operations
// to reduce N to 0 by replacing
// N by its divisor at each step
 
let MAX = 10000001
let sieve= new Array(MAX);
 
// Function to calculate sieve
function makeSieve()
{
    let i, j;
    sieve[0] = 0;
    sieve[1] = 1;
 
    for (i = 2; i < MAX; i++)
        sieve[i] = 0;
 
    for (i = 2; i * i <= MAX; i++) {
        if (!sieve[i]) {
            sieve[i] = i;
            for (j = i * i; j < MAX; j += i)
                if (!sieve[j])
                    sieve[j] = i;
        }
    }
    for (i = 2; i < MAX; i++) {
        if (!sieve[i])
            sieve[i] = 1;
        else
            sieve[i] = i / sieve[i];
    }
}
 
// Function to count minimum operations
function minOperations(N)
{
    if (N < 0)
        return -1;
 
    let count = 0;
    makeSieve();
    while (N) {
        N -= sieve[N];
        count++;
    }
    return count;
}
 
 
// Driver code
    let N = 8;
 
// Function call
    document.write(minOperations(N));
     
    // This code is contributed by jana_sayantan.
</script>

4

Complejidad de tiempo: O(N * log(log N)
Espacio auxiliar: O(MAX), donde MAX es el límite para el tamiz (aquí MAX = 10000001).