163 votos

Algoritmo para calcular el número de divisores de un número determinado

¿Cuál sería el algoritmo óptimo (rendimiento) para calcular el número de divisores de un número determinado?

Va a ser genial si usted podría proporcionar pseudocódigo o un enlace a un ejemplo.

EDIT: Todas las respuestas han sido muy útiles, gracias. Voy a implementar la criba de Atkin y entonces voy a usar algo similar a lo que indica Jonathan Leffler. El enlace publicado por Justin Bozonier tiene más información sobre lo que quería.

74voto

Justin Bozonier Puntos 4037

Dmitriy es correcta y que vas a querer que el Tamiz de Atkin para generar la primer lista, pero no creo que se ocupa de todo el tema. Ahora que usted tiene una lista de números primos tendrá que ver cuántos de esos primos de actuar como un divisor (y la frecuencia).

He aquí algunos de python para el algo Vistazo aquí y la búsqueda de "Tema: matemáticas - necesidad de divisores algoritmo". Sólo contar el número de elementos en la lista en lugar de devolverlos sin embargo.

He aquí un Dr. en Matemáticas que explica exactamente qué es lo que usted necesita hacer matemáticamente.

Esencialmente se reduce a si su número n es:
n = a^x * b^y * c^z
(donde a, b, y c son n del primer divisores de x, y, y z es el número de veces que el divisor se repite) a continuación, el recuento total de todos los divisores de:
(x + 1) * (y + 1) * (z + 1).

Edit: por CIERTO, para hallar a,b,c,etc usted querrá hacer lo que equivale a un codicioso algo si estoy entender esto correctamente. Comience con su mayor divisor primo y lo multiplicamos por sí mismo hasta que se de una mayor multiplicación excedería el número n. A continuación, pasar a la siguiente más baja y factor de veces el anterior primer ^ número de veces que se multiplica por el actual primer y mantener multiplicando por el primer hasta el próximo superará n... etc. Mantener un seguimiento del número de veces que se multiplica el divisores juntos y se aplican los números en la fórmula anterior.

No es el 100% seguro de algo acerca de mi descripción, pero si que no es que es algo similar .

47voto

user11318 Puntos 4804

Hay muchas más técnicas de factorización de el tamiz de Atkin. Por ejemplo, supongamos que queremos factor 5893. Además de sus sqrt es 76.76... Ahora vamos a tratar de escribir 5893 como un producto de plazas. Bien (77*77 - 5893) = 36 6 al cuadrado, por lo que 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71. Si eso no hubiera trabajado tendríamos que ver si el 78*78 - 5893 era un cuadrado perfecto. Y así sucesivamente. Con esta técnica se puede probar rápidamente por factores cerca de la raíz cuadrada de n mucho más rápido que por las pruebas individuales de los números primos. Si se combina esta técnica para descartar grandes primos con un colador, usted tendrá una mejor método de factorización que con el tamiz solo.

Y este es sólo uno de un gran número de técnicas que se han desarrollado. Este es uno bastante sencillo. Se necesitaría mucho tiempo para aprender, digamos, un número suficiente teoría para entender la incorporación de técnicas basadas en curvas elípticas. (Sé que existen. No los entiendo.)

Por lo tanto, a menos que usted está tratando con enteros pequeños, no intentar solucionar ese problema yo mismo. En lugar de eso me iba a tratar de encontrar una manera de utilizar algo como el PARI biblioteca que ya tiene una solución muy eficaz implementado. Con que puedo factor aleatorio 40 dígitos como 124321342332143213122323434312213424231341 en sobre .05 segundos. (Su factorización, en caso de que usted preguntaba, es 29*439*1321*157907*284749*33843676813*4857795469949. Estoy bastante seguro de que no figura esta usando el tamiz de Atkin...)

33voto

Kendall Puntos 171

@Yasky

Su función de divisores tiene un bug que no funciona correctamente para cuadrados perfectos.

Prueba:

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    for (int i(1); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

27voto

Tyler Puntos 16516

No estoy de acuerdo que la criba de Atkin es el camino a seguir, porque fácilmente podría tomar más tiempo para revisar todos los números en [1, n] para primalidad que sería para reducir el número de divisiones.

Un código esto es que, aunque un poco hackier, es generalmente mucho más rápido:

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ps Eso es trabajo código python para resolver este problema.

10voto

dongilmore Puntos 492

Esta muy interesante, la pregunta es mucho más difícil de lo que parece, y no ha sido contestada. La pregunta puede ser tenidos en cuenta en la 2 muy diferentes preguntas.

1 N dado, encontrar la lista L de N factores primos

2 dado L, calcular el número de combinaciones únicas

Todas las respuestas que veo hasta ahora se refieren a #1 y no mencionan no es manejable para los números enormes. De tamaño moderado N, incluso números de 64 bits, es fácil; por el enorme N, el problema de la factorización puede tomar "para siempre". Cifrado de clave pública depende de esto.

Pregunta #2 necesite más discusión. Si L contiene sólo números únicos a los que, se trata de un simple cálculo mediante la combinación de la fórmula para la elección de k objetos de n elementos. En realidad, necesita de la suma de los resultados de la aplicación de la fórmula al variar k de 1 a sizeof(L). Sin embargo, L contener varias apariciones de varios de los números primos. Por ejemplo, L = {2,2,2,3,3,5} es el de la factorización de N = 360. Ahora este problema es bastante difícil!

La reformulación de #2, de la colección de C que contiene k elementos, de tal manera que un elemento tiene un " duplicados, y en el punto b ha b " duplicados, etc. ¿cuántas combinaciones únicas de 1 a k-1 elementos hay? Por ejemplo, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} debe producirse sólo una vez y sólo una vez si L = {2,2,2,3,3,5}. Cada uno de esos único sub-colección es un único divisor de N por la multiplicación de los elementos de la sub-colección.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X