¿Qué es un algoritmo eficiente para encontrar divisores de cualquier número?

Answer 1

Si el número es grande, usa la factorización prima, luego encuentra todas las potencias posibles que se pueden hacer, entonces tienes todos los divisores.

Tomemos por ejemplo el número 120:

[matemáticas] 120 = 2 ^ {3} \ veces 5 ^ {1} \ veces 3 ^ {1} \\ 40 = 2 ^ {3} \ veces 5 ^ {1} \ veces 3 ^ {0} \\ 24 = 2 ^ {3} \ veces 5 ^ {0} \ veces 3 ^ {1} \\ 8 = 2 ^ {3} \ veces 5 ^ {0} \ veces 3 ^ {0} \\ 60 = 2 ^ { 2} \ veces 5 ^ {1} \ veces 3 ^ {1} \\ 20 = 2 ^ {2} \ veces 5 ^ {1} \ veces 3 ^ {0} \\ 12 = 2 ^ {2} \ veces 5 ^ {0} \ veces 3 ^ {1} \\ 4 = 2 ^ {2} \ veces 5 ^ {0} \ veces 3 ^ {0} \\ 30 = 2 ^ {1} \ veces 5 ^ {1 } \ times 3 ^ {1} \\ 10 = 2 ^ {1} \ times 5 ^ {1} \ times 3 ^ {0} \\ 6 = 2 ^ {1} \ times 5 ^ {0} \ times 3 ^ {1} \\ 2 = 2 ^ {1} \ veces 5 ^ {0} \ veces 3 ^ {0} \\ 15 = 2 ^ {0} \ veces 5 ^ {1} \ veces 3 ^ {1} \\ 5 = 2 ^ {0} \ times 5 ^ {1} \ times 3 ^ {0} \\ 3 = 2 ^ {0} \ times 5 ^ {0} \ times 3 ^ {1} \\ 1 = 2 ^ {0} \ veces 5 ^ {0} \ veces 3 ^ {0} \\ [/ matemáticas]

Esos son los 16 divisores de 120, producidos al observar las potencias posibles (de 3,1,1 a 0,0,0).

Si observa las posibilidades de los exponentes posibles, es 4 para 3 (0,1,2,3), 2 para 1 (0,1) y 2 para el otro 1 (0,1), por lo que hay un total de 16 divisores .

Todo lo que debe hacer es primero factorizar primero, luego recorrer todos los exponentes posibles.

Con este método, puede obtener los divisores de incluso números muy grandes con relativa rapidez, pero aún así no funcionaría tan bien para productos de números primos muy grandes, ya que la factorización prima todavía tomaría un tiempo.

Encontrar los divisores del número [matemática] 10 ^ {12} [/ matemática] tomaría iteraciones [matemática] 10 ^ {6} [/ matemática] usando el otro método, pero usando este método solo tomaría menos de 300 iteraciones .

Este es el método que se me ocurrió para pasar los problemas del concurso de programación.

Alguien más en el pasado debe haber descubierto algo similar, creo.

Answer 2

A lo que te refieres se llama factorización entera. Actualmente el algoritmo más eficiente es el algoritmo de Shor, pero requiere una computadora cuántica. Es un tema de gran interés para los criptógrafos, y encontrará muchos algoritmos diferentes en el artículo de Wikipedia anterior (aparentemente, el mejor tiempo de ejecución para un algoritmo general, medido por análisis, es el tamiz de campo de número general).

Sin embargo, creo que el algoritmo propuesto por Prajwal Renukanand proporciona un buen equilibrio entre velocidad y simplicidad (aunque de ninguna manera soy un experto).

Answer 3

No estoy seguro si es el más eficiente, pero podría pensar en un algoritmo [matemático] O (\ sqrt {N}) [/ matemático].

1. Crea una lista dinámica S.
2. Recorra i = 1 a [math] \ sqrt {N} [/ math]:
   yo. Compruebe si N es divisible por i, en caso afirmativo, agregue i a la lista S, además, es obvio que N / i también se puede agregar. (Debe haber una comprobación para una raíz cuadrada exacta de N, solo para evitar agregar i (= N / i) dos veces).

Fragmento de código:

  ArrayList  al = new ArrayList  ();

 for (long i = 1; i <= n / i; i ++) {
  
     if (n% i == 0) {
      
         if (n / i == i) {
             al.add (i);
         } más {
             al.add (i);
			 al.add (n / i);
		 }
     }
 }

Answer 4

Para el número de divisores, es un algoritmo de tamiz modificado.

#define lim 1000000

int div [lim + 1];

para (i = 2; i <= lim; i ++) // primer bucle
para (j = i; j <= lim; j = j + i) // segundo bucle
div [j] ++; // recuento de almacenamiento

¿Cómo funciona?
Al igual que el Algoritmo de tamiz que marca todos los múltiplos de un número como FALSO que establece que el número no era primo, este algoritmo funciona de manera similar a la cantidad de números en el rango de 1 a lim son divisibles por i (en el primer bucle) y almacena su cuenta en div array.

Entonces, si tienes que saber que no. de divisores de 100 solo tiene que generar div [100] +1 y obtendrá su respuesta.
¡Espero que esto ayude!

Answer 5

  de matemáticas import sqrt
 def perfecto (n):  
     c = redondo (sqrt (n))
     s = 1    
	 para i en rango (2, c + 1):        
		 si n% i == 0:            
			 s = s + i + n // i
     devoluciones
 n = 20000000
 imprimir (perfecto (n))

SALIDA: 29902216

TIEMPO TOMADO: 0.0015053749084472656

ide use https://www.google.co.in/url?sa=…

¡ESPERO QUE ME GUSTA!

Answer 6

Hola
Este es el algoritmo más eficiente que conozco.

1. Comience ingresando un número n
2. Deje que un límite variable int sea sqrt (n)
3. Ejecute un ciclo de i = 1 a i = limit
    3.1 si n es divisible por i
3.1.1 Imprimir i
3.1.2 si i y n / i son desiguales, imprima n / i también.
4. Fin.

Answer 7

Si usted es un programador, puede hacerlo fácilmente usando C ++. Para su ayuda, le estoy escribiendo el código exacto en el que debe establecer un rango de números, y luego mostrará todos sus divisores.

[código]

#include

usando el espacio de nombres estándar;

int main ()

{

int a, b, i, j;

cout << "Ingrese el número inicial:";

cin >> a;

cout << "Ingrese el número final:";

cin >> b;

para (i = a; i <= b; i ++)

{

cout << "Los divisores de" << i << "son:";

para (j = 1; j <= i; j ++)

{

si (i% j == 0)

{

cout << "" << j;

}

}

cout << endl;

}

sistema (“Pausa”);

devuelve 0;

}

[/código]