que - Algoritmo para encontrar los factores de un número dado. ¿Método más corto?

numeros primos

Question

¿Cuál podría ser la lógica más simple y eficiente en el tiempo para averiguar los factores de un Número dado? ¿Hay algún algoritmo que exista, basado en el mismo?

En realidad, mi verdadero problema es descubrir el no. de factores que existen para un número dado ..

Así que cualquier algoritmo, por favor hágamelo saber sobre esto ...

Gracias.

Answer 1

En realidad, mi verdadero problema es descubrir el no. de factores que existen para un número dado ..

Bueno, esto es diferente. Sea n el número dado.

Si n = p1^e1 * p2^e2 * ... * pk^ek , donde cada p es un número primo, entonces el número de factores de n es (e1 + 1)*(e2 + 1)* ... *(ek + 1) . Más sobre esto here .

Por lo tanto, es suficiente encontrar los poderes en los que aparece cada factor primo. Por ejemplo:

read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
power = 0; // suppose the power i appears at is 0
while (n % i == 0) // while we can divide n by i
{
n = n / i // divide it, thus ensuring we''ll only check prime factors
++power // increase the power i appears at
}
num_factors = num_factors * (power + 1) // apply the formula
}
if (n > 1) // will happen for example for 14 = 2 * 7
{
num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}

Por ejemplo, tomar 18 . 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6 . De hecho, los 6 factores de 18 son 1, 2, 3, 6, 9, 18 .

Aquí hay un pequeño punto de referencia entre mi método y el método descrito y publicado por @Maciej. El tiene la ventaja de ser más fácil de implementar, mientras que el mío tiene la ventaja de ser más rápido si el cambio solo se repite en los números primos, como he hecho para esta prueba:

 class Program
{
static private List<int> primes = new List<int>();
private static void Sieve()
{
bool[] ok = new bool[2000];
for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually)
{
if (!ok[i])
{
primes.Add(i);
for (int j = i; j < 2000; j += i)
ok[j] = true;
}
}
}
private static int IVlad(int n)
{
int initial_n = n;
int factors = 1;
for (int i = 0; primes[i] * primes[i] <= n; ++i)
{
int power = 0;
while (initial_n % primes[i] == 0)
{
initial_n /= primes[i];
++power;
}
factors *= power + 1;
}
if (initial_n > 1)
{
factors *= 2;
}
return factors;
}
private static int Maciej(int n)
{
int factors = 1;
int i = 2;
for (; i * i < n; ++i)
{
if (n % i == 0)
{
++factors;
}
}
factors *= 2;
if (i * i == n)
{
++factors;
}
return factors;
}
static void Main()
{
Sieve();
Console.WriteLine("Testing equivalence...");
for (int i = 2; i < 1000000; ++i)
{
if (Maciej(i) != IVlad(i))
{
Console.WriteLine("Failed!");
Environment.Exit(1);
}
}
Console.WriteLine("Equivalence confirmed!");
Console.WriteLine("Timing IVlad...");
Stopwatch t = new Stopwatch();
t.Start();
for (int i = 2; i < 1000000; ++i)
{
IVlad(i);
}
Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
Console.WriteLine("Timing Maciej...");
t.Reset();
t.Start();
for (int i = 2; i < 1000000; ++i)
{
Maciej(i);
}
Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
}
}

Resultados en mi máquina:

Prueba de equivalencia ...
¡Equivalencia confirmada!
Sincronización IVlad ...
Milisegundos totales: 2448
Cronometraje Maciej ...
Milisegundos totales: 3951
Pulse cualquier tecla para continuar . . .

Answer 2

Aquí es un fruto de mi breve discusión con | / | ad :)

read given number in n
int divisorsCount = 1;
int i;
for(i = 2; i * i < n; ++i)
{
if(n % i == 0)
{
++divisorsCount;
}
}
divisorsCount *= 2;
if(i * i == n)
{
++divisorsCount;
}

Answer 3

Cuidado, esta respuesta no es útil / rápida para un solo valor de n.

Método 1 :

Puede obtenerlo en O (polylog (n)) si mantiene una tabla de consulta (para el primer factor primo de un número).

Si gcd (a, b) == 1, entonces no. de factores de a * b = (número de factores de a) * (número de factores de b)

Por lo tanto, para un número dado a * b, si gcd (a, b)! = 1 entonces podemos tener otros dos números p y q donde p = a y q = b / gcd (a, b). Por lo tanto, gcd (p, q) == 1. Ahora, podemos encontrar recursivamente el número de factores para p y q.

Sólo se requerirá una pequeña cantidad de esfuerzos para garantizar que ni p ni q sean 1.

PS Este método también es útil cuando necesita conocer el número de factores de todos los números del 1 al n. Sería un orden de O (nlogn + O (tabla de consulta)).

Método 2 : (No tengo propiedad para esto.)

Si tiene la búsqueda del primer factor primo hasta n, entonces puede saber que son todos los factores primos en O (logn) y, por lo tanto, encontrar el número de factores a partir de ellos.

PS Google ''Factorización en logn'' para una mejor explicación.

Answer 4

El algoritmo de Euclides debería ser suficiente.

Answer 5

Hay una gran cantidad de algoritmos disponibles, desde una simple idea de prueba hasta algoritmos muy sofisticados para grandes cantidades. Eche un vistazo a la factorización de enteros en Wikipedia y elija una que se adapte a sus necesidades.

Aquí hay una implementación de C # corta pero ineficiente que encuentra el número de factores primos. Si necesita el número de factores (no los factores primos), debe almacenar los factores primos con su multiplicidad y luego calcular el número de factores.

var number = 3 * 3 * 5 * 7 * 11 * 11;
var numberFactors = 0;
var currentFactor = 2;
while (number > 1)
{
if (number % currentFactor == 0)
{
number /= currentFactor;
numberFactors++;
}
else
{
currentFactor++;
}
}

Answer 6

Puedes echar un vistazo a este algoritmo .