performance - tiene - halla los divisores de un numero

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

Question

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

Sería genial si pudieras proporcionar pseudocódigo o un enlace a algún ejemplo.

EDIT: todas las respuestas han sido muy útiles, gracias. Estoy implementando el Sieve of Atkin y luego voy a usar algo similar a lo que Jonathan Leffler indicó. El enlace publicado por Justin Bozonier tiene más información sobre lo que quería.

Answer 1

¿No es solo una cuestión de factorizar el número, determinar todos los factores del número? A continuación, puede decidir si necesita todas las combinaciones de uno o más factores.

Entonces, 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

Depende de usted combinar los factores para determinar el resto de la respuesta.

Answer 2

@Kendall

Probé tu código e hice algunas mejoras, ahora es aún más rápido. También probé con el código @ هومن جاویدپور, esto 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 3

@Yasky

La función de divisores tiene un error porque no funciona correctamente para cuadrados perfectos.

Tratar:

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

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

Hace un tiempo hubo una pregunta principal e hice una prueba de tiempo: para enteros de 32 bits, al menos determinar si era primo era más lento que la fuerza bruta. Hay dos factores en juego:

1) Mientras que un humano tarda un tiempo en hacer una división, es muy rápido en la computadora, de manera similar al costo de buscar la respuesta.

2) Si no tiene una tabla principal, puede crear un ciclo que se ejecute por completo en la caché L1. Esto lo hace más rápido.

Answer 5

Aquí hay un algoritmo directo O (sqrt (n)). Lo usé para resolver el projecteuler.net/problem=12

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 6

Aquí hay una función que escribí. es la peor complejidad de tiempo es O (sqrt (n)), el mejor tiempo, por otro lado es O (log (n)). Te da todos los divisores principales 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 7

Creo que este será útil y preciso

script.pyton

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

Answer 8

Creo que esto es lo que estás buscando. Hago exactamente lo que pediste. Cópialo y pégalo en el Bloc de notas. Guarda como * .bat.Run.Enter Number.Multiplica el proceso por 2 y esa es la cantidad de divisores. Lo hice a propósito para que determine los divisores más rápido:

Por favor tenga en cuenta que un CMD variado no puede soportar valores superiores a 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 9

Desea el tamiz de Atkin, descrito aquí: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Answer 10

Dmitriy tiene razón en que querrás que Sieve of Atkin genere la lista principal, pero no creo que eso solucione todo el problema. Ahora que tiene una lista de números primos, necesitará ver cuántos de esos números primos actúan como divisores (y con qué frecuencia).

Aquí hay un pitón para el algoritmo Busque aquí y busque "Asunto: matemática - necesita el algoritmo de divisores". Simplemente cuente la cantidad de elementos en la lista en lugar de devolverlos.

Aquí hay un Dr. Math que explica qué es exactamente lo que necesita hacer matemáticamente.

Básicamente se reduce a si su número n es:
n = a^x * b^y * c^z
(donde a, b y c son los divisores primos de nyx, yyz son la cantidad de veces que se repite ese divisor), entonces el recuento total de todos los divisores es:
(x + 1) * (y + 1) * (z + 1) .

Editar: Por cierto, para encontrar a, b, c, etc. querrás hacer lo que equivale a un algo avaro si entiendo esto correctamente. Comience con su divisor principal más grande y multiplíquelo por sí mismo hasta que una multiplicación adicional exceda el número n. Luego vaya al siguiente factor más bajo y multiplicado por el número de veces anterior ^ multiplicado por el primo actual y siga multiplicando por el primo hasta que el siguiente exceda n ... etc. Lleve un registro del número de veces que multiplica el número divisores juntos y aplicar esos números en la fórmula anterior.

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

Answer 11

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

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

Este algoritmo funcionará correctamente para el número que son cuadrado perfecto así como también para los números que no son cuadrados perfectos.

Tenga en cuenta que el límite superior del bucle se establece en la raíz cuadrada del número para que el algoritmo sea más eficiente.

Tenga en cuenta que almacenar el límite superior en una variable separada 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 del ciclo anterior para, también puede usar el siguiente ciclo, que es incluso más eficiente ya que elimina la necesidad de encontrar la raíz cuadrada del número.

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

Answer 12

El tamiz de Atkin es una versión optimizada del tamiz de Eratóstenes que da todos los números primos hasta un número entero dado. Deberías poder googlear esto para más detalles.

Una vez que tenga esa lista, es una cuestión simple dividir su número por cada primo para ver si es un divisor exacto (es decir, el resto es cero).

Los pasos básicos para calcular los divisores para un número (n) son [este es un pseudocódigo convertido a partir de código real, así que espero no haber 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 13

Esta es la forma más básica de calcular los divisores de números:

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 14

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 15

Esta pregunta interesante es mucho más difícil de lo que parece, y no ha sido respondida. La pregunta se puede factorizar en 2 preguntas muy diferentes.

1 dado N, encuentre la lista de factores primos de L of N

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

Todas las respuestas que veo hasta ahora se refieren al n. ° 1 y no menciono que no es manejable para números enormes. Para N de tamaño moderado, incluso números de 64 bits, es fácil; para una N enorme, el problema del factoring puede tomar "para siempre". El cifrado de clave pública depende de esto.

La pregunta n. ° 2 necesita más discusión. Si L contiene solo números únicos, es un cálculo simple usando la fórmula de combinación para elegir k objetos de n elementos. En realidad, debe sumar los resultados de la aplicación de la fórmula al variar k de 1 a tamaño de (L). Sin embargo, L generalmente contendrá múltiples ocurrencias de primos múltiples. Por ejemplo, L = {2,2,2,3,3,5} es la factorización de N = 360. ¡Ahora este problema es bastante difícil!

Repetición de # 2, dada la colección C que contiene k elementos, tal que el elemento a tiene un ''duplicados y el elemento 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} deben aparecer una vez y solo una vez si L = {2,2 , 2,3,3,5}. Cada una de esas subcolecciones únicas es un divisor único de N al multiplicar los elementos en la subcolección.

Answer 16

Esto es algo que se me ocurrió basado en la respuesta de Justin. Puede requerir alguna 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 17

Hay muchas más técnicas para factorizar que el tamiz de Atkin. Por ejemplo, supongamos que queremos factorizar 5893. Bueno, su sqrt es 76,76 ... Ahora trataremos de escribir 5893 como un producto de cuadrados. Bien (77 * 77 - 5893) = 36 que es 6 al cuadrado, entonces 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Si eso no hubiera funcionado, habríamos analizado si 78 * 78 - 5893 era un cuadrado perfecto. Y así. Con esta técnica, puedes probar rápidamente los factores cercanos a la raíz cuadrada de n mucho más rápido que al probar primos individuales. Si combina esta técnica para descartar números primos grandes con un tamiz, tendrá un método de factorización mucho mejor que con el tamiz solo.

Y esta es solo una de las muchas técnicas que se han desarrollado. Este es bastante simple. Le tomará mucho tiempo aprender, por ejemplo, la teoría de números suficiente para comprender las técnicas de factorización basadas en curvas elípticas. (Sé que existen. No los entiendo).

Por lo tanto, a menos que estés tratando con enteros pequeños, yo no trataría de resolver ese problema yo mismo. En cambio, trataría de encontrar una forma de usar algo como la biblioteca PARI que ya tiene implementada una solución altamente eficiente. Con eso puedo factorizar un número aleatorio de 40 dígitos como 124321342332143213122323434312213424231341 en aproximadamente 0.05 segundos. (Su factorización, en caso de que se lo haya preguntado, es 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Estoy bastante seguro de que esto no se solucionó con el tamiz de Atkin ...)

Answer 18

Los divisores hacen algo espectacular: se dividen completamente. Si desea verificar el número de divisores para un número, n , es claramente redundante abarcar todo el espectro, 1...n . No he hecho ninguna investigación exhaustiva para esto, pero he resuelto el problema 12 del Proyecto Euler en Triangular Numbers . Mi solución para la prueba mayor de 500 divisores se ejecutó durante 309504 microsegundos (~ 0.3s). Escribí esta función de divisor para 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 contra los números primos. Pero dado que los números triangulares no están impresos, cumplió su propósito sin problemas. Desde mi perfil, creo que lo hizo bastante bien.

Felices vacaciones.

Answer 19

Los libros de texto de teoría de números llaman a la función de conteo de divisores tau. El primer hecho interesante es que es multiplicativo, es decir. τ (ab) = τ (a) τ (b), cuando a y b no tienen un factor común. (Prueba: cada par de divisores de ayb da un divisor distinto de ab).

Ahora note que para pa prime, τ (p ** k) = k + 1 (las potencias de p). Por lo tanto, puede calcular fácilmente τ (n) a partir de su factorización.

Sin embargo, factorizar grandes cantidades puede ser lento (la seguridad de la critoprafia RSA depende del producto de dos primos grandes que son difíciles de factorizar). Eso sugiere este algoritmo optimizado

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

Answer 20

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

• Crea 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, usaría el tamiz de Atkin)
• Cuente todos los números primos menores o iguales que la raíz cuadrada del número y multiplíquelo por dos. Si la raíz cuadrada del número es un número entero, resta uno de la variable de conteo.

Debería funcionar / o /

Si lo necesita, puedo codificar algo mañana en C para demostrarlo.

Answer 21

No estoy de acuerdo en que el tamiz de Atkin sea el camino a seguir, porque fácilmente podría tomar más tiempo verificar cada número en [1, n] en primalidad que reducir el número por divisiones.

Aquí hay un código que, aunque un poco más complicado, generalmente 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 Eso funciona código python para resolver este problema.

Answer 22

Pruebe algo en esta línea:

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 23

Puede precalcular los primos hasta la raíz sqaure del máximo posible N y calcular el exponente de cada factor primo de un número. El número de divisores de n (n = p1 ^ a p2 ^ b p3 ^ c ...) es (a + 1) (b + 1) (c + 1) porque es lo mismo que contar la forma de combinar el primer números de estos factores (y esto contará el número de divisores). Esto es muy rápido si calcula previamente los números primos

Información más detallada sobre 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 24

Puedes probar este. Es un poco hackish, pero es bastante rápido.

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

Answer 25

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

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

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

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

Answer 26

Una vez que tenga la factorización prima, hay una manera de encontrar la cantidad de divisores. Agregue uno a cada uno de los exponentes en cada factor individual y luego multiplique los exponentes juntos.

Por ejemplo: 36 Prime Factorization: 2 ^ 2 * 3 ^ 2 Divisores: 1, 2, 3, 4, 6, 9, 12, 18, 36 Número de divisores: 9

Añade uno a cada exponente 2 ^ 3 * 3 ^ 3 Multiplica los exponentes: 3 * 3 = 9

Answer 27

el método del número primo es muy claro aquí. P [] es una lista de número primo menor o igual que 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 28

SOLO una línea
He pensado muy cuidadosamente sobre su pregunta y he tratado de escribir un código de código altamente eficiente y eficaz. Para imprimir todos los divisores de un número determinado en la pantalla, ¡necesitamos solo una línea de código! (use la opción -std = c99 mientras 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 números de divisores, puede usar la siguiente función muy muy rápida (funciona correctamente para todos los números enteros, 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 trata el número dado como un divisor (funciona correctamente para todos los números enteros, 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 funcionan correctamente para todos los números enteros positivos, excepto el número 1 y 2, por lo que es funcional para todos los números que son mayores que 2, pero si necesita cubrir 1 y 2, puede usar 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 :)