Dado un entero positivo N . En una operación resta N con su divisor más alto que no sea N y 1 . La tarea es encontrar las operaciones mínimas requeridas para reducir N exactamente a un número primo .
Ejemplos:
Entrada: N = 38
Salida: 1
Explicación: El divisor más alto de 38 es 19, así que réstelo (38 – 19) = 19. 19 es un número primo.
Entonces, número de operaciones requeridas = 1.Entrada: N = 69
Salida: 2
Enfoque: Este problema se puede resolver usando conceptos matemáticos simples. Siga los pasos a continuación para resolver el problema dado.
- Al principio, compruebe si N ya es primo o no.
- Si N ya es un número primo, devuelve 0 .
- De lo contrario, inicialice una variable, digamos count = 0 para almacenar la cantidad de operaciones requeridas.
- Inicialice una variable digamos i=2 y ejecute un ciclo while hasta que N!=i
- Ejecute el ciclo while y en cada iteración reste el valor actual de N con su divisor más grande.
- Calcule los pasos e incremente el conteo en 1 .
- Devuelve la cuenta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function check whether a number // is prime or not bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to square root of n for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } // Function to minimum operations required // to reduce the number to a prime number int minOperation(int N) { // Because 1 cannot be converted to prime if (N == 1) return -1; // If given number is already prime // return 0 if (isPrime(N) == true) { return 0; } // If number is not prime else { // Variable for total count int count = 0; int i = 2; // If number is not equal to i while (N != i) { // If N is completely divisible by i while (N % i == 0) { // Temporary variable to store // current number int temp = N; // Update the number by decrementing // with highest divisor N -= (temp / i); // Increment count by 1 count++; if (isPrime(N)) return count; } i++; } // Return the count return count; } } // Driver Code int main() { int N = 38; cout << minOperation(N); return 0; }
Java
// Java program for the above approach import java.util.Arrays; class GFG { // Function check whether a number // is prime or not public static boolean isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to square root of n for (int i = 2; i <= Math.sqrt(n); i++) if (n % i == 0) return false; return true; } // Function to minimum operations required // to reduce the number to a prime number public static int minOperation(int N) { // Because 1 cannot be converted to prime if (N == 1) return -1; // If given number is already prime // return 0 if (isPrime(N) == true) { return 0; } // If number is not prime else { // Variable for total count int count = 0; int i = 2; // If number is not equal to i while (N != i) { // If N is completely divisible by i while (N % i == 0) { // Temporary variable to store // current number int temp = N; // Update the number by decrementing // with highest divisor N -= (temp / i); // Increment count by 1 count++; if (isPrime(N)) return count; } i++; } // Return the count return count; } } // Driver Code public static void main(String args[]) { int N = 38; System.out.println(minOperation(N)); } } // This code is contributed by gfgking.
Python3
# python program for the above approach import math # Function check whether a number # is prime or not def isPrime(n): # Corner case if (n <= 1): return False # Check from 2 to square root of n for i in range(2, int(math.sqrt(n)) + 1): if (n % i == 0): return False return True # Function to minimum operations required # to reduce the number to a prime number def minOperation(N): # Because 1 cannot be converted to prime if (N == 1): return -1 # If given number is already prime # return 0 if (isPrime(N) == True): return 0 # If number is not prime else: # Variable for total count count = 0 i = 2 # If number is not equal to i while (N != i): # If N is completely divisible by i while (N % i == 0): # Temporary variable to store # current number temp = N # Update the number by decrementing # with highest divisor N -= (temp // i) # Increment count by 1 count += 1 if (isPrime(N)): return count i += 1 # Return the count return count # Driver Code if __name__ == "__main__": N = 38 print(minOperation(N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; public class GFG { // Function check whether a number // is prime or not public static bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to square root of n for (int i = 2; i <= Math.Sqrt(n); i++) if (n % i == 0) return false; return true; } // Function to minimum operations required // to reduce the number to a prime number public static int minOperation(int N) { // Because 1 cannot be converted to prime if (N == 1) return -1; // If given number is already prime // return 0 if (isPrime(N) == true) { return 0; } // If number is not prime else { // Variable for total count int count = 0; int i = 2; // If number is not equal to i while (N != i) { // If N is completely divisible by i while (N % i == 0) { // Temporary variable to store // current number int temp = N; // Update the number by decrementing // with highest divisor N -= (temp / i); // Increment count by 1 count++; if (isPrime(N)) return count; } i++; } // Return the count return count; } } // Driver Code public static void Main(string []args) { int N = 38; Console.WriteLine(minOperation(N)); } } // This code is contributed by AnkThon
Javascript
<script> // JavaScript program for the above approach // Function check whether a number // is prime or not const isPrime = (n) => { // Corner case if (n <= 1) return false; // Check from 2 to square root of n for (let i = 2; i <= parseInt(Math.sqrt(n)); i++) if (n % i == 0) return false; return true; } // Function to minimum operations required // to reduce the number to a prime number const minOperation = (N) => { // Because 1 cannot be converted to prime if (N == 1) return -1; // If given number is already prime // return 0 if (isPrime(N) == true) { return 0; } // If number is not prime else { // Variable for total count let count = 0; let i = 2; // If number is not equal to i while (N != i) { // If N is completely divisible by i while (N % i == 0) { // Temporary variable to store // current number let temp = N; // Update the number by decrementing // with highest divisor N -= parseInt(temp / i); // Increment count by 1 count++; if (isPrime(N)) return count; } i++; } // Return the count return count; } } // Driver Code let N = 38; document.write(minOperation(N)); // This code is contributed by rakeshsahni </script>
Producción
1
Complejidad de tiempo: O (sqrtN)
Espacio Auxiliar: O(1)