Dado un entero positivo N , la tarea es encontrar la altura del árbol de factores del entero N dado .
Ejemplos:
Entrada: N = 20
Salida: 3
Explicación: La altura del árbol de factores de 20 que se muestra en la imagen de abajo es 3.Entrada: N = 48
Salida: 5
Enfoque: El problema dado se puede resolver siguiendo los pasos que se describen a continuación:
- Inicialice una variable, digamos altura como 0 que almacena la altura del árbol de factores del entero N dado .
- Iterar sobre todos los valores de i en el rango [2, √N] y realizar los siguientes pasos:
- Encuentre el divisor más pequeño de N y, si existe, incremente el valor de la altura en 1 .
- Si existe un divisor i , repita el paso anterior actualizando el valor de N a N / i , hasta que N > 1 .
- Si no existen divisores de N , rompa el ciclo .
- Después de completar los pasos anteriores, imprima el valor de la altura como respuesta.
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 to find the height of the // Factor Tree of the integer N int factorTree(int N) { // Stores the height of Factor Tree int height = 0; // Loop to iterate over values of N while (N > 1) { // Stores if there exist // a factor of N or not bool flag = false; // Loop to find the smallest // factor of N for (int i = 2; i <= sqrt(N); i++) { // If i is a factor of N if (N % i == 0) { N = N / i; flag = true; break; } } // Increment the height height++; // If there are no factors of N // i.e, N is prime, break loop if (!flag) { break; } } // Return Answer return height; } // Driver Code int main() { int N = 48; cout << factorTree(N); return 0; }
Java
// Java program for the above approach public class Main { // Function to find the height of the // Factor Tree of the integer N static int factorTree(int N) { // Stores the height of Factor Tree int height = 0; // Loop to iterate over values of N while (N > 1) { // Stores if there exist // a factor of N or not boolean flag = false; // Loop to find the smallest // factor of N for (int i = 2; i <= Math.sqrt(N); i++) { // If i is a factor of N if (N % i == 0) { N = N / i; flag = true; break; } } // Increment the height height++; // If there are no factors of N // i.e, N is prime, break loop if (!flag) { break; } } // Return Answer return height; } public static void main(String[] args) { int N = 48; System.out.println(factorTree(N)); } } // This code is contributed by mukesh07.
Python3
# Python 3 program for the above approach from math import sqrt # Function to find the height of the # Factor Tree of the integer N def factorTree(N): # Stores the height of Factor Tree height = 0 # Loop to iterate over values of N while (N > 1): # Stores if there exist # a factor of N or not flag = False # Loop to find the smallest # factor of N for i in range(2,int(sqrt(N))+1,1): # If i is a factor of N if (N % i == 0): N = N // i flag = True break # Increment the height height += 1 # If there are no factors of N # i.e, N is prime, break loop if (flag==False): break # Return Answer return height # Driver Code if __name__ == '__main__': N = 48 print(factorTree(N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach using System; class GFG { // Function to find the height of the // Factor Tree of the integer N static int factorTree(int N) { // Stores the height of Factor Tree int height = 0; // Loop to iterate over values of N while (N > 1) { // Stores if there exist // a factor of N or not bool flag = false; // Loop to find the smallest // factor of N for (int i = 2; i <= Math.Sqrt(N); i++) { // If i is a factor of N if (N % i == 0) { N = N / i; flag = true; break; } } // Increment the height height++; // If there are no factors of N // i.e, N is prime, break loop if (!flag) { break; } } // Return Answer return height; } static void Main() { int N = 48; Console.Write(factorTree(N)); } } // This code is contributed by decode2207.
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the height of the // Factor Tree of the integer N function factorTree(N) { // Stores the height of Factor Tree let height = 0; // Loop to iterate over values of N while (N > 1) { // Stores if there exist // a factor of N or not let flag = false; // Loop to find the smallest // factor of N for (let i = 2; i <= Math.sqrt(N); i++) { // If i is a factor of N if (N % i == 0) { N = Math.floor(N / i); flag = true; break; } } // Increment the height height++; // If there are no factors of N // i.e, N is prime, break loop if (!flag) { break; } } // Return Answer return height; } // Driver Code let N = 48; document.write(factorTree(N)); // This code is contributed by Potta Lokesh </script>
Producción:
5
Complejidad de tiempo: O(√N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anurag2311 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA