Algoritmo para encontrar todos los divisores exactos de un entero dado

7 minutos de lectura

avatar de usuario
jairaj

Quiero encontrar todos los divisores exactos de un número. Actualmente tengo esto:

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i<=n/2)
    {
        if(n%i==0)
                  printf("%d,",i);
        i++;
     }
   getch();
}

¿Hay alguna forma de mejorarlo?

avatar de usuario
Rndm

Primero, su código debe tener la condición de i <= n/2de lo contrario, puede perder uno de los factores, por ejemplo, 6 no se imprimirá si n = 12.

Ejecute el bucle hasta la raíz cuadrada del número (es decir, i <= sqrt(n)) e imprima ambos i y n/i (ambos serán múltiplos de n).

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

Nota :

  • Para un cuadrado perfecto, de modo que la raíz cuadrada no se imprima dos veces, la verificación adicional se realiza al final del bucle para i*i == n como lo sugiere @chepner.
  • Si desea que todos los factores estén en orden ascendente, almacene los valores en una matriz y luego, al final del ciclo, ordene todos los números y visualícelos.

  • tu puedes cambiar printf("%d,", i);printf("%d,", n/i); para printf("%d,", i); if(i != n/i){printf("%d,", n/i);}.Para un cuadrado perfecto, no imprimirá el doble de la raíz.

    – MYMNeo

    28 de julio de 2012 a las 8:22

  • Puede evitar las múltiples comprobaciones de n/i !=i iterando sobre i < sqrt(n)lo que implica que n/i != iluego comprobando i=sqrt(n) fuera del ciclo while como un caso de un solo borde.

    – Chepner

    28 de julio de 2012 a las 16:22

  • ¿Cuál es la prueba de que todos los divisores se pueden encontrar haciendo bucles sqrt(n) veces solamente? por favor explique.

    – Bruce Wayne

    13 de abril de 2015 a las 18:28

  • Cómo ? Imprimirá 2 y 4. ¿Se refiere al hecho de que 1 y 8 no se imprimirán?

    – Rndm

    6 de noviembre de 2015 a las 6:24

  • @Rndm – tenga en cuenta que i <= sqrt(n) promueve i a un doble. podrías usar i <= (int)sqrt(n) para evitar esto. Sería más rápido cambiar if (i != (n / i)) para if (i*i != n) .

    – rcgldr

    6 de noviembre de 2017 a las 22:42


avatar de usuario
hombreypc

Encontrar todos los divisores usando “encontrar todos los factores primos” en C (más rápido) y hasta 18 dígitos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) {
    unsigned int lastdiv = 0;
    divisors[lastdiv++] = 1;
    unsigned long long powerfactor = 1;
    unsigned long long number = N;
    while ((number & 1) == 0) {
        powerfactor <<= 1;
        divisors[lastdiv++] = powerfactor;
        number >>= 1;
    }

    unsigned long long factor = 3; unsigned long long upto = lastdiv;
    powerfactor = 1;
    while (factor * factor <= number) {
        if (number % factor == 0) {
            powerfactor *= factor;
            for (unsigned int i = 0; i < upto; i++)
                divisors[lastdiv++] = divisors[i] * powerfactor;
            number /= factor;
        }
        else {
            factor += 2; upto = lastdiv;
            powerfactor = 1;
        }
    }

    if (number > 1) {
        if (number != factor) {
            upto = lastdiv;
            powerfactor = 1;
        }
        powerfactor *= number;
        for (unsigned int i = 0; i < upto; i++)
            divisors[lastdiv++] = divisors[i] * powerfactor;
    }
    return lastdiv;
}

int cmp(const void *a, const void *b) {
    if( *(long long*)a-*(long long*)b < 0 ) return -1;
    if( *(long long*)a-*(long long*)b > 0 ) return 1;
    return 0;
}

int main(int argc, char *argv[]) {
    unsigned long long N = 2;
    unsigned int Ndigit = 1;
    if (argc > 1) {
        N = strtoull(argv[1], NULL, 10);
        Ndigit = strlen(argv[1]);
    }
    unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344,
                             2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680};

    unsigned long long divisors[maxdiv[Ndigit]];
    unsigned int size = FindDivisors(divisors, N);
    printf("Number of divisors = %u\n", size);

    qsort(divisors, size, sizeof(unsigned long long), cmp);
    for (unsigned int i = 0; i < size; i++)
        printf("%llu ", divisors[i]);
    printf("\n");

    return 0;
}

La búsqueda lineal simple se puede mejorar eliminando primero todos los factores de 2. Eso se puede hacer con un simple cambio de bits o contando ceros de entrenamiento con una buena función intrínseca. Eso es muy rápido en cualquier caso. Luego ejecute el algoritmo sugerido por shg (que funcionará mucho más rápido ahora que las potencias de dos no están presentes) y combine el resultado con todas las potencias de dos posibles (no olvide este paso). Ayuda mucho para las entradas que tienen muchos ceros de entrenamiento, pero incluso ayuda si no los tienen: ya no tendría que probar ningún divisor par, por lo que el ciclo se vuelve la mitad de largo.

Descartar algunos factores bajos constantes (pero mayores que 2) también puede ayudar. Es casi seguro que el módulo con una constante está optimizado por el compilador (o si no, puede hacerlo usted mismo), pero lo que es más importante, eso significa que quedan menos divisores para probar. No olvides combinar ese factor con los divisores que encuentres.

También puede factorizar el número por completo (use su algoritmo favorito, probablemente Rho de Pollard sería el mejor), y luego imprimir todos los productos (excepto el producto vacío y el producto completo) de los factores. Esto tiene una buena posibilidad de terminar siendo más rápido para entradas más grandes: el algoritmo Rho de Pollard encuentra factores muy rápidamente en comparación con una búsqueda lineal simple, generalmente hay menos factores que los divisores adecuados, y el último paso (enumerar los productos) solo implica matemáticas rápidas (sin divisiones). Esto ayuda principalmente para números con factores muy pequeños, que Rho encuentra más rápido.

  • ¿Podría dar un ejemplo de cómo eliminar todos los factores de 2 por desplazamiento de bits? Las operaciones de bits son más rápidas, por lo que seguramente mejoraría el rendimiento.

    – jairaj

    28 de julio de 2012 a las 8:44

  • @jairaj dice que toma 24, la raíz cuadrada es casi 5 pero no del todo, por lo que tendría que probar los divisores 2, 3 y 4 (generarían 12, 8 y 6, respectivamente). Si eliminas todas las potencias de dos, te queda 3. Solo 3. La raíz cuadrada de 3 es menor que 2, así que no necesitas probar ninguna divisores Así que pasaste de 3 divisiones lentas a cero divisiones + un par de turnos (primero para eliminar las potencias de dos, luego para volver a agregarlas). Una victoria clara.

    – harold

    28 de julio de 2012 a las 8:54


  • @jairaj en cuanto a la combinación: tendrías 3 potencias de 2: 2, 4 y 8. Todos estos son divisores. Ahora multiplique cada uno de ellos por 3 (“todos” los demás divisores, de los cuales solo hay uno), para obtener 6, 12 y 24. Luego deseche 24 porque no es un divisor propio.

    – harold

    28 de julio de 2012 a las 9:05

avatar de usuario
pato

El código presentado en una de las respuestas tiene un error que es difícil de ver a primera vista. Si sqrt(n) es un divisor válido; pero norte no es un número cuadrado perfecto, entonces se omiten dos resultados.

Por ejemplo, prueba n = 15y mira lo que pasa; sqrt(15) = 3por lo que el último valor del ciclo while es 2. La siguiente instrucción ejecutada if (i * i == n) será ejecutado como if(3 * 3 == 15). Entonces, 3 no aparece como divisor, también se perdió 5.

Lo siguiente manejará correctamente el caso general de enteros positivos.

 {
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

  int count = 2;
     //long childsum = 0;
           long _originalvalue = sum;
     dividend = "1";
     for (int i = 2; i < sum; i++)
     {
         if (_originalvalue % i == 0)
         {
             sum = _originalvalue / i;
             //sum = childsum;
             dividend = dividend + "," + i+","+sum;
             if (sum == i)
             {
                 count++;
             }
             else
             {
                 count = count + 2;
             }
         }
     }
     return count;

avatar de usuario
manohar e

Cuando el número dado es impar, incluso podemos saltarnos los números pares. Una ligera improvisación en el código aceptado 🙂

Aquí está el código Java para encontrar factores del número dado.

import java.util.Scanner;
public class Factors {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-- > 0) {
            int n = scanner.nextInt();
            if(n % 2 == 0) {
                for(int i = 1; i <= Math.sqrt(n); i++) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
            else {
                for(int i = 1; i <= Math.sqrt(n); i=i+2) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
        }
    }
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad