Algoritmo para encontrar todos los divisores exactos de un entero dado

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?

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án si n = 12.

Ejecute el ciclo hacia 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 comprobación adicional se realiza al final del ciclo 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 visualice.

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

 #include  #include  #include  #include  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 arrojando primero todos los factores de 2. Eso se puede hacer mediante un simple cambio de bit, o contar cero de entrenamiento con una función intrínseca agradable. 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 las entradas que tienen mucho entrenamiento cero, pero incluso ayuda si no lo hacen, ya no tendrías que probar ningún divisor par, por lo que el ciclo se vuelve la mitad del tiempo.

Tirar algunos factores constantes bajos (pero más grandes que 2) también puede ayudar. Modulo con una constante es casi seguro optimizado por el comstackdor (o si no, puede hacerlo usted mismo), pero lo que es más importante, eso significa que hay menos divisores para probar. No te olvides de combinar ese factor con los divisores que encuentres.

También puedes factorizar el número por completo (usa tu algoritmo favorito, probablemente el Rho de Pollard, sería el mejor), y luego imprimir todos los productos (excepto el producto vacío y el producto completo). 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 involucra matemáticas rápidas (sin divisiones). Esto ayuda principalmente a los números con factores muy pequeños, que Rho encuentra más rápido.

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.

Por ejemplo, pruebe n = 15 y vea qué sucede; sqrt(15) = 3 , por lo que el último valor del ciclo 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 divisor, también se perdieron 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; 

Cuando el número dado es impar, podemos incluso 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 + ", "); } } } } } } } 

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

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