Función de c# que acepta un número entero n y devuelve el número más bajo que puede ser dividido por los números divisores 1..n.

Answer

1. 

   davy.ai

   June 1, 2023 at 3:53 am

   En primer lugar, es genial que ya haya creado una función que funciona efectivamente para números más pequeños.

   Un enfoque para mejorar el rendimiento de la función es usar la factorización de números primos. El mínimo común múltiplo de un conjunto de números se puede encontrar utilizando su factorización en números primos.

   Por ejemplo, si n=4, los números son 1, 2, 3 y 4. La factorización en números primos de cada número es:

   1 = 1
   2 = 2
   3 = 3
   4 = 2^2

   Los números 2 y 3 solo aparecen una vez en la factorización en números primos, mientras que 2 aparece dos veces. Por lo tanto, solo necesitamos multiplicar 2 y 3, y 2 dos veces para obtener el mínimo común múltiplo de 1, 2, 3 y 4, que es 12.

   Este enfoque puede mejorar significativamente el rendimiento de la función, especialmente para números más grandes, porque calcular la factorización en números primos de un número es mucho más rápido que hacer un bucle a través de todos los números de 1 a n para verificar si hay una división par.

   Aquí hay una función actualizada que utiliza este enfoque:

   public static string Smallest(int n)
   {
       int[] primes = GetPrimes(n);
       int[] powers = new int[primes.Length];
   
       for (int i = 1; i <= n; i++)
       {
           int[] factorization = GetPrimeFactorization(i, primes);
           for (int j = 0; j < primes.Length; j++)
           {
               if (factorization[j] > powers[j])
               {
                   powers[j] = factorization[j];
               }
           }
       }
   
       int result = 1;
       for (int i = 0; i < primes.Length; i++)
       {
           result *= (int)Math.Pow(primes[i], powers[i]);
       }
   
       return result.ToString();
   }
   
   private static int[] GetPrimes(int n)
   {
       bool[] isPrime = new bool[n + 1];
       for (int i = 2; i <= n; i++)
       {
           isPrime[i] = true;
       }
   
       for (int i = 2; i * i <= n; i++)
       {
           if (isPrime[i])
           {
               for (int j = i * i; j <= n; j += i)
               {
                   isPrime[j] = false;
               }
           }
       }
   
       int count = 0;
       for (int i = 2; i <= n; i++)
       {
           if (isPrime[i])
           {
               count++;
           }
       }
   
       int[] primes = new int[count];
       int index = 0;
       for (int i = 2; i <= n; i++)
       {
           if (isPrime[i])
           {
               primes[index] = i;
               index++;
           }
       }
   
       return primes;
   }
   
   private static int[] GetPrimeFactorization(int n, int[] primes)
   {
       int[] factorization = new int[primes.Length];
   
       for (int i = 0; i < primes.Length; i++)
       {
           int prime = primes[i];
           int count = 0;
           while (n % prime == 0)
           {
               count++;
               n /= prime;
           }
           factorization[i] = count;
       }
   
       return factorization;
   }
   

   Esta función primero calcula todos los números primos hasta n utilizando el algoritmo de la Criba de Eratóstenes. Luego, hace un bucle a través de todos los números de 1 a n y calcula su factorización en números primos utilizando la matriz de números primos.

   La matriz de potencias realiza un seguimiento de la potencia máxima de cada número primo que aparece en la factorización en números primos de cualquiera de los números de 1 a n. Una vez que se han calculado todas las factorizaciones en números primos, se construye el mínimo común múltiplo multiplicando cada número primo a su potencia correspondiente.

   En general, este enfoque debería ser mucho más rápido que el bucle a través de todos los números de 1 a n, especialmente para valores más grandes de n.

Comments are closed.