saber - divisores exactos c++

Algoritmo para encontrar todos los divisores exactos de un número entero dado

Question

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 manera de mejorarlo?

Answer 1

Cuando el número dado es impar, incluso podemos omitir números pares. Una ligera improvisación en el código aceptado :)

Aquí está el código de 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 + ", ");
                        }
                    }
                }
            }
        }
    }
}

Answer 2

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 n no es un número cuadrado perfecto, entonces se omiten dos resultados.

Ej. Intenta n = 15 , y ve qué pasa; sqrt(15) = 3 , por lo que el último valor del bucle while es 2. La siguiente instrucción ejecutada if (i * i == n) se ejecutará como if(3 * 3 == 15) . Entonces 3 no está listado como un divisor, también se perdió 5.

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

 {
   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();
}

Answer 3

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;
}

Answer 4

Esta es mi nueva versión de C #. Gracias a Rndm es casi 50 veces más rápido que mi primer intento.

public static long GetDivisors(long number)
    {
        long divisors = 0;

        long boundary = (long)Math.Sqrt(number);

        for (int i = 1; i <= boundary; i++)
        {
            if (number % i == 0)
            {
                divisors++;
                if(i != (number / i))
                {
                    if (i * i != number)
                    {
                        divisors++;
                    }
                }
            }
        }

        return divisors;
    }

Answer 5

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 los entrenamientos de cero con una buena función intrínseca. Eso es muy rápido en cualquier caso. Luego ejecute el algoritmo sugerido por shg (que se ejecutará mucho más rápido ahora que las potencias de dos no están presentes), y combine el resultado con todas las potencias posibles de dos (no olvide este paso). Ayuda mucho para los insumos que tienen una gran cantidad de entrenamientos de cero, pero incluso ayuda si no lo hacen; ya no tendrías que probar ningún divisor par, por lo que el bucle se vuelve la mitad.

Desechar algunos factores bajos constantes (pero mayores de 2) también puede ayudar. El módulo con una constante es casi seguro que está optimizado por el compilador (o, si no, puede hacerlo usted mismo), pero lo más importante es que hay 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 el Rho de Pollard sería el mejor), y luego imprima todos los productos (excepto el producto vacío y el producto completo) de los factores. Esto tiene una buena probabilidad 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, usualmente hay menos factores que los divisores apropiados, y el último paso (enumerar los productos) solo implica matemáticas rápidas (sin divisiones). Esto ayuda principalmente a números con factores muy pequeños, que Rho encuentra más rápido.

Answer 6

Primero, su código debe tener la condición de i <= n/2 , de lo contrario, puede pasar por alto 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 tanto i como 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, para 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 en orden ascendente almacenen los valores en una matriz, al final del bucle ordene todos los números y la pantalla.

Answer 7

  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;