actualmente estoy usando el siguiente código, pero es muy lento para un gran númeroNecesito un algoritmo óptimo para encontrar el mayor divisor de un número N de preferencia en C++ o C#
static int divisor(int number)
{
int i;
for (i = number/2; i >= 1; i--)
{
if (number % i == 0)
{
break;
}
}
return i;
}
primer pensamiento se encuentra la divisor d más pequeño (no igual a 1 por supuesto), entonces N/d será el divisor más grande que estás buscando.
Por ejemplo, si N es divisible por 3, entonces necesitará 2 iteraciones para encontrar la respuesta; en su caso, se trataría de N/6 iteraciones.
Editar: Para mejorar aún más su algoritmo que se pueden recorrer sólo los números impares (después de comprobar si el número es par) o, mejor aún, si usted tiene la lista de los números primos precalculados entonces se puede iterar a través de ellos solo porque el divisor más pequeño es obviamente un número primo.
Esto tiene la ventaja adicional de verificar primero los divisores "más probables". (es decir, 2 es "más probable" que sea un divisor de un número arbitrario que, por ejemplo, 2189) – Justin
@Vladimir: esto tiene un reclamo oculto de que los divisores pequeños son más densos (en promedio, para TODOS los números), es decir, es más rápido encontrar un divisor comenzando desde 2 hacia arriba que comenzando desde N/2 hacia abajo. Si bien esto parece intuitivamente razonable, ¿tiene algunas matemáticas para apoyarlo? – davka
Y en realidad, esto puede mejorarse aún más si hay una función que calcula previamente un número razonable de primos (o simplemente hace una tabla de números primos), y encuentra cuál de ellos divide el número en lugar de recorrer todo el números impares. – supercheetah
Para limitar su espacio de búsqueda, debe comenzar en 2 y trabajar hasta la raíz cuadrada del número. Hay muchos más números (en un espacio de búsqueda finito) divisibles por 2 que por 27, por lo que es más probable obtener un divisor bajo que uno alto, estadísticamente hablando.
Cuando procesa (por ejemplo) 1,000,000, encontrará una gran diferencia cuando use la raíz cuadrada, en lugar de la mitad del valor. La diferencia es entre un espacio de búsqueda de 500,000 para su método y 1,000 para el método de raíz cuadrada es considerable.
Otra ventaja es reducir a la mitad el espacio de búsqueda en el frente descontando múltiplos de dos. Entonces, cuando tienes tu divisor más bajo, el más alto es simplemente el número dividido por eso.
Pseudocódigo:
if n % 2 == 0: # Halve search space straight up.
print n/2
else:
i = 3 # Start at 3.
while i * i <= n: # Or use i <= sqrt(n), provided sqrt is calc'ed once
if n % i == 0:
print n/i # If multiple, get opposite number, print and stop
break
i = i + 2 # Only need to process odd numbers
Supongamos que el número es 10^9, ¿no encontraría mi método su divisor más grande más rápido, es decir, 5 * (10^8)? – Ronzii
@Ronzi. El número 10^9 sería capturado inmediatamente por este código ya que es divisible por dos. Yo devolvería 10^9/2 (5x10^8) en la segunda declaración. Es por eso que comienza bajo, no a n/2. La probabilidad de encontrar factores bajos es mucho mejor. – paxdiablo
Buen consejo. ¡Pude encontrarlo realmente rápido! – Ronzii
No sabe si es la solución óptima pero probablemente sería mejor partida a las 2 y luego va hacia arriba como por ejemplo:
static int divisor(int number)
{
int i;
for (i = 2; i <sqrt(number); i++)
{
if (number % i == 0)
{
break;
}
}
return number/i;
}
para que funcione también con primos:
static int divisor(int number)
{
int i;
for (i = 2; i <=sqrt(number); i++)
{
if (number % i == 0)
{
return number/i;
}
}
return 1;
}
@Bunnit: El código anterior no producirá los resultados correctos – bjskishore123
No sea obtuso, @bjsk, _specify_ en qué condiciones no funciona. – paxdiablo
@ bjskishore123: Sí, el valor de retorno es incorrecto si el número es primo, pero esto podría arreglarse fácilmente marcando til sqrt (número) +1 luego verificando ese valor al regresar, o retornando donde está el salto y fuera del for (si es un primo). Lo acabo de escribir como un ejemplo rápido. –
Optimización: un número impar no puede tener un número par como el divisor más grande. Utilice este filtro en el número temprano. Entonces, si se da un número impar.
En primer lugar hacer la división con 2.
Entonces disminuir i por cada 2 en bucle
Ésta es mejorará la velocidad de los números impares.
También el divisor real más grande de números pares es la mitad de ellos mismos. – Calmarius
Una gran optimización (no estoy seguro de si es completamente óptima, tendrías que preguntarle a un matemático para eso) es buscar hacia arriba utilizando solo números primos. Como dijeron Vladimir y Bunnit, es mejor buscar hacia arriba, porque lo encontrarás mucho más rápido. Luego, devuelve el inverso (number/i). Sin embargo, si ya has intentado 2 y estás seco, no tiene sentido intentar 4 o 6. De manera similar, si has probado 3, no tiene sentido intentar 6 o 9.
Por lo tanto, si el tiempo de ejecución es una gran preocupación, podría tener una lista de las primeras 100 primos codificadas en su programa. Prueba cada uno de ellos. Si no encuentra una respuesta para entonces, entonces puede simplemente incrementarla en 2 (omitiendo los números pares).
Básicamente se ha llegado al problema de la "factorización de grandes cantidades", que es la base del cifrado de clave pública de hoy en día y se sabe (o se espera) que es un problema computacionalmente difícil. De hecho espero que no encuentre una solución mucho mejor, de lo contrario toda la infraestructura de seguridad del mundo colapsará ... :)
Sí, el OP está lidiando con la lentitud de factorizar números grandes, pero * no * en la escala en cualquier lugar cercano equivalente a factorizar los números utilizados en sistemas criptográficos de clave pública como RSA y DSA. – mctylr
Uno de los métodos estándar de la industria para encontrar factores de grandes números es el algoritmo del tamiz cuadrático.
tener una lectura de esta:
http://en.wikipedia.org/wiki/Quadratic_sieve
P. S. también debes considerar qué tan grandes son tus números. Los diferentes algoritmos de factorización tienden a funcionar bien para un cierto tamaño, y no para otros. Como se señala en el artículo de QS wiki, este método generalmente es el más rápido para números de menos de 100 dígitos decimales.
un vistazo aquí: - http://programmingpraxis.com/contents/themes/#Prime%20Numbers
programación Praxis establece regularmente retos de programación para las personas a resolver para un poco de diversión en un viernes a mediodía. Este problema particular surge mucho y existen varios algoritmos bien conocidos para resolverlo ilustrados con código.
Algunas optimizaciones adicionales:
1. If even then divisable by 2.
2. If the sum of the digits is divisable by 3, then number is divisble by 3 (ie 78 = 7 + 8 = 15 = 1 + 5 = 6 which is divisable by 3)
3. If it ends in 0 or 5 it is divisable by 5
Gordon.
El mejor algoritmo dependerá de qué tan grandes sean realmente sus números.
Este problema es básicamente tan difícil como los enteros de factorización; si tiene algún algoritmo de factorización, será bastante fácil de usar para construir el mayor divisor no trivial. Una vez más, cuál de todos los algoritmos de factorización conocidos que emplea para un número debe depender de su "envergadura", ya que para diferentes escalas, estos sofisticados algoritmos probablemente tendrán diferentes actuaciones.
Probablemente encontrará varias (tal vez diferentes) respuestas a su pregunta en buenos libros sobre criptografía, algoritmos y teoría de números computacionales.
De nuevo, dependiendo de su escala, incluso podría ser una opción simple precomputar una gran lista de números primos, guardarla y luego dar una búsqueda de número de entrada dentro de esta lista para el divisor más pequeño - que tendrá inmediatamente el mayor divisor pop-up, también.
Encuentra el primer primo que divide el número N. Digamos que primo es p. Divide N por d. Este es el resultado requerido que desea.
¿N no será N el mayor divisor de una N? Tal vez "devolver el número"; es la función que estás buscando? – SadSido
El divisor más grande de N es N en sí ... – Vladimir
Primera mejora: no comience en 'número/2', sino en' sqrt (número) '. – phimuemue