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

Question

¿Cuál sería el más óptimo del algoritmo (en cuanto al rendimiento) para calcular el número de divisores de un número dado?

Que va a ser grande si usted podría proporcionar pseudocódigo o un link a un ejemplo.

EDITAR:Todas las respuestas han sido muy útil, muchas gracias.Estoy implementando el Tamiz de Atkin y, a continuación, voy a usar algo similar a lo que Jonathan Leffler indicado.El enlace publicado por Justin Bozonier tiene más información sobre lo que yo quería.

Answer 1

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

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

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

Esencialmente se reduce a si el número de 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 es:
(x + 1) * (y + 1) * (z + 1).

Editar:Por CIERTO, para hallar a,b,c,etc usted querrá hacer lo que equivale a un codicioso algo si estoy entendiendo esto correctamente.Comience con su mayor divisor primo y se multiplica por sí mismo hasta 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.Realizar el seguimiento del número de veces que se multiplica el divisores juntos y se aplican los números en la fórmula de arriba.

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

Answer 2

Hay un mucho más técnicas de factorización que 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 los cuadrados.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 mirado si 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 números primos con ayuda de un tamiz, usted tendrá una mucho mejor factoring método 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.Te tomaría mucho tiempo para aprender, digamos, un número suficiente de 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ía resolver el problema yo mismo.En su lugar me gustaría tratar de encontrar una manera de utilizar algo como el PARI la 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 tenía la figura de este cabo utilizando el tamiz de Atkin...)

Answer 3

@Yasky

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

Probar:

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

    if (x == 1) return 1;

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

    return numberOfDivisors;
}

Answer 4

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

Aquí un poco de código que, aunque ligeramente hackier, por lo general es 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 Que de trabajo de código en python para resolver este problema.

Answer 5

Interesante esta 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 que no es manejable para un enorme número.Moderadamente de tamaño N, incluso números de 64 bits, es fácil;para enormes N, el problema de la factorización puede tomar "para siempre".El cifrado de clave pública depende de esto.

Pregunta #2 necesita más discusión.Si L contiene sólo números únicos, es un simple cálculo mediante la combinación de la fórmula para la elección de k objetos de n elementos.En realidad, usted necesita a 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 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 tiene 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 multiplicando los elementos de la sub-colección.

Answer 6

Una respuesta a su pregunta depende en gran medida del tamaño del entero.Métodos para números pequeños, por ejemplo,a menos de 100 bits, y para los números de ~1000 bits (como el usado en la criptografía) son completamente diferentes.

• visión general: http://en.wikipedia.org/wiki/Divisor_function

• los valores para los pequeños n y algunas referencias útiles: A000005:d(n) (también llamado tau(n) o sigma_0(n)), el número de divisores de n.

• ejemplo real: factorización de números enteros

Answer 7

Aquí está una recta hacia adelante O(sqrt(n)) algoritmo.He utilizado este para resolver proyecto de euler

def divisors(n):
    count=2 # accounts for 'n' and '1'
    i=2
    while(i**2 < n):
        if(n%i==0):
            count+=2
        i+=1
    count+=(1 if i**2==n else 0)
    return count  

Answer 8

SÓLO una línea
He pensado muy cuidadosamente acerca de su pregunta y he tratado de escribir una alta eficiencia y rendimiento en el trozo de código Para imprimir todos los divisores de un número dado en la pantalla tenemos una sola línea de código!(utilice la opción -std=c99 mientras se compila a través de gcc)

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

para encontrar el número de divisores puede utilizar el siguiente muy muy rápido de la función(trabajo correctamente para todo número entero excepto 1 y 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

o, si usted trata de un número determinado como un divisor(trabajo correctamente para todo número entero excepto 1 y 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

NOTA:las dos funciones anteriores funciona correctamente para todo número entero positivo, excepto el número 1 y 2 por lo que es funcional para todos los números que son mayores que 2 pero si usted Necesita para cubrir 1 y 2 , puede utilizar una de las siguientes funciones( un poco más lento)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

O

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

lo pequeño es hermoso :)

Answer 9

El tamiz de Atkin es una versión optimizada de la criba de Eratóstenes, que le da todos los números primos menores que un entero dado.Usted debe ser capaz de google para obtener más detalles.

Una vez que tenga la lista, es una simple cuestión de dividir el número por cada uno de los prime para ver si es un divisor exacto (es decir, el resto es cero).

Los pasos básicos para el cálculo de los divisores de un número (n) son [esto es pseudocódigo convierte de código real así que espero que no se han introducido errores]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

Answer 10

Usted puede probar este.Es un poco hackish, pero es razonablemente rápido.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

Answer 11

Una vez que usted tiene la factorización en primos, hay una manera de encontrar el número de divisores.Agregar uno a cada uno de los exponentes en cada factor individual y, a continuación, se multiplican los exponentes juntos.

Por ejemplo:36 Descomposición En Factores Primos:2^2*3^2 Divisores:1, 2, 3, 4, 6, 9, 12, 18, 36 Número de Divisores:9

Agregar uno a cada exponente 2^3*3^3 Se multiplican los exponentes:3*3 = 9

Answer 12

Antes de comprometerse con una solución de considerar que el Tamiz enfoque podría no ser una buena respuesta en el caso típico.

Hace un tiempo hubo un primer pregunta y me hice una prueba de tiempo--para enteros de 32 bits, al menos, la determinación de si fue el primer fue más lento que la fuerza bruta.Hay dos factores pasando:

1) Mientras que un ser humano toma un tiempo para hacer una división que son muy rápidos en el equipo--similar al costo de buscar la respuesta.

2) Si usted no tiene un primer tabla, usted puede hacer un bucle que se ejecuta totalmente en la caché L1.Esto hace que sea más rápido.

Answer 13

Esta es una solución eficiente:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}

Answer 14

Divisores de hacer algo espectacular:se dividen por completo.Si desea comprobar el número de divisores de un número, n, obviamente , es redundante para abarcar todo el espectro, 1...n.Yo no he hecho ninguna investigación en profundidad para esto, pero he resuelto Proyecto de Euler del problema 12 en Números Triangulares.Mi solución para el más de 500 divisores la prueba se ejecutó para 309504 microsegundos (~0,3 s).Escribí este divisor función de la solución.

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

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

    return numberOfDivisors * 2;
}

Para cada algoritmo, hay un punto débil.Pensé que esto era débil en contra de los números primos.Pero desde triangular números no son de impresión, cumplido su propósito a la perfección.De mis perfiles, creo que lo hizo bastante bien.

Felices Fiestas.

Answer 15

Desea que el Tamiz de Atkin, se describe a continuación: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Answer 16

el primer número de método es muy claro aquí .P[] es una lista de los números primos menores o iguales que el sq = sqrt(n) ;

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .

Answer 17

La teoría de los números de los libros de texto de llamada el divisor función de recuento de tau.El primer dato interesante es que es multiplicativa, es decir,.τ(ab) = τ(a)τ(b) , cuando a y b no tienen ningún factor común.(Prueba:cada par de divisores de a y b da una distinta divisor de ab).

Ahora tenga en cuenta que para p un primo, τ(p**k) = k+1 (los poderes de p).Así que usted puede fácilmente calcular τ(n) a partir de su factorización.

Sin embargo factorizar grandes números puede ser lenta (la seguridad de RSA crytopraphy depende del producto de dos números primos de ser de difícil factorise).Que sugiere que esta optimizado algoritmo

1. Prueba si el número es primo (rápido)
2. Si es así, devuelve 2
3. De lo contrario, factorise el número (lento si varios grandes factores primos)
4. Calcular τ(n) a partir de la factorización

Answer 18

El siguiente es un programa en C para encontrar el número de divisores de un número dado.

La complejidad del algoritmo anterior es O(sqrt(n)).

Este algoritmo funciona correctamente para el número de los que están cuadrado perfecto, así como a los números que no son de cuadrado perfecto.

Tenga en cuenta que el upperlimit del bucle se establece a la raíz cuadrada de número en el algoritmo más eficiente.

Tenga en cuenta que el almacenamiento de la upperlimit en una variable independiente también ahorra tiempo, no debe llamar a la función sqrt en la sección de condición del bucle for, esto también ahorra su tiempo de cálculo.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

En lugar de la anterior de bucle también se puede utilizar el siguiente bucle, que es aún más eficiente, ya que esto elimina la necesidad de encontrar la raíz cuadrada del número.

for(i=2;i*i<=n;i++)
{
    ...
}

Answer 19

Aquí es una función que escribí.es el peor tiempo de la complejidad es O(sqrt(n)),mejor tiempo en el otro lado es O(log(n)).Te da todos los primos divisores junto con el número de su ocurrencia.

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}

Answer 20

Esta es la forma más básica de calcular el número de divissors:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}

Answer 21

@Kendall

He probado el código y hecho algunas mejoras, ahora es incluso más rápido.También he probado con @هومن جاویدپور código, este también es más rápido que su código.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}

Answer 22

No se trata simplemente de una cuestión de factoring el número de la determinación de todos los factores de la serie?A continuación, puede decidir si usted necesita todas las combinaciones de uno o más factores.

Así, un posible algoritmo sería:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

Es entonces que se combinan los factores para determinar el resto de la respuesta.

Answer 23

Esto es algo que se me ocurrió con base en Justin respuesta.Esto puede requerir algunos de optimización.

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))

Answer 24

Yo creo que esto es lo que usted está buscando.Me hace exactamente lo que usted pidió.Copiar y Pegar en el Bloc de notas.Guardar como *.bate.Ejecute.Introduzca El Número.Multiplique el proceso por el 2, y es el número de divisores.La hice a propósito para que los que determinar los divisores más rápido:

Nota de Pls que un CMD varriable cant valores de soporte sobre 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start

Answer 25

supongo que esto será útil, así como precisa

secuencia de comandos.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Answer 26

Trate de algo a lo largo de estas líneas:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}

Answer 27

Usted puede precompute de los números primos hasta el sqaure raíz de la máxima posible N y calcular el exponente de cada factor primo de un número.El número de divisores de n (n = p1^un p2^b p3^c...) es (a+1)(b+1)(c+1) porque es el mismo como el conde de la manera de combinar los números primos de estos factores (y se tendrá en cuenta el número de divisores).Esto es muy rápido si usted precompute de los números primos

Información más detallada acerca de este método:

https://mathschallenge.net/library/number/number_of_divisors

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

http://primes.utm.edu/glossary/xpage/tau.html

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int divisors_count(const vector<int>& primes, int n)
{
    int divisors = 1;
    for (int i = 0; i < primes.size(); ++i) {
        int factor = primes[i];
        int factor_exponent = 0;
        while (n % factor == 0) {
            ++factor_exponent;
            n /= factor;
        }
        divisors *= (factor_exponent + 1);
    }
    if (n > 1) 
        return 2*divisors; // prime factor > sqrt(MAX_N)
    return divisors;
}

int main()
{
    const int MAX_N = 1e6;
    int max_factor = sqrt(MAX_N);

    vector<char> prime(max_factor + 1, true);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            for (int j = 3*i; j <= max_factor; j += 2*i) {
                prime[j] = false;
            }   
        }
    }

    vector<int> primes;
    primes.reserve(max_factor/2);
    primes.push_back(2);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            primes.push_back(i);
        }
    }

    int n;
    while (cin >> n) {
        cout << divisors_count(primes, n) << endl;
    }
}

Answer 28

No sé el método MÁS eficiente, pero yo haría lo siguiente:

• Crear una tabla de números primos para encontrar todos los números primos menores o iguales a la raíz cuadrada del número (Personalmente, yo uso el Tamiz de Atkin)
• Contar todos los números primos menores o iguales a la raíz cuadrada del número y de la que se multiplican por dos.Si la raíz cuadrada del número es un entero, entonces restar uno a la variable de conteo.

Debería funcionar \o/

Si usted necesita, puedo código de algo hasta mañana en C a demostrar.