Problemas con los números primos

StackOverflow https://stackoverflow.com/questions/1877255

  •  18-09-2019
  •  | 
  •  

Pregunta

Estoy tratando de escribir un programa para encontrar el factor primo más grande de un número muy grande, y han intentado varios métodos con mayor o menor éxito. Todos los que he encontrado hasta ahora han sido increíblemente lento. Tenía un pensamiento, y me pregunto si esto es un enfoque válido: 

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Este enfoque permitiría tener una entrada, y podría hacer lo siguiente:

200 -> 100 -> 50 -> 25 -> 5 (regreso)

90 -> 45 -> 15 -> 5 (regreso)

Se divide currentNum repetidamente por el número divisible más pequeño (más a menudo 2 o 3) hasta que en sí currentNum es primo (no hay ningún número primo divisible menor que la raíz cuadrada de currentNum), y se supone que este es el factor primo más grande del de entrada original.

¿Esto siempre funciona? Si no es así, alguien puede darme un contraejemplo?

-

EDIT:. Por muy grande, quiero decir acerca de 2 ^ 40, o 10 ^ 11

¿Fue útil?

Solución

Esto siempre va a funcionar debido a la único primer teorema de factorización .

Otros consejos

El método funciona, pero será lenta. "¿Cuán grandes son sus números?" determina el método de empleo:

Por supuesto que va a funcionar (ver Marcos Byers respuesta ), pero para las entradas "muy grandes" que puede tomar demasiado tiempo. Debe tener en cuenta que su llamada a getLowestDivisiblePrimeNumber() oculta otro bucle, por lo que este se ejecuta en O (n ^ 2), y que en función de lo que quiere decir con "muy grande" que puede tener que trabajar en bignums que será lento.

Se podría acelerarlo un poco, señalando que el algoritmo no necesita comprobar los factores más pequeño que el último encontrado.

Usted está tratando de encontrar las href="http://en.wikipedia.org/wiki/Prime_factor" de un número. Lo que está proponiendo el trabajo voluntad, pero todavía será lenta para un gran número .... usted debe estar agradecido por esto, ya que la mayor seguridad moderna se basa en este ser un problema difícil.

A partir de una búsqueda rápida que acabo de hacer, la manera más rápida conocida para factorizar un número es mediante el uso de método de la curva elíptica.

Usted podría tratar de lanzar su número en esta demostración: http://www.alpertron.com .ar / ECM.HTM .

Si eso te convence, usted podría intentar robar o bien el código (que no es divertido, que proporcionan un enlace a ella!) O leer sobre la teoría de la otra parte. Hay un artículo de Wikipedia sobre él aquí: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization pero estoy demasiado estúpido para entenderlo. Afortunadamente, es su problema, no el mío! :)

Lo que pasa con Proyecto Euler es que por lo general hay un método de fuerza bruta obvia a hacer el problema, que tendrá casi siempre. A medida que las preguntas se hacen más difíciles, que tendrá que poner en práctica soluciones inteligentes.

Una manera de resolver este problema es utilizar un bucle que siempre encuentra el factor más pequeño (entero positivo) de un número. Cuando el factor más pequeño de un número es ese número, entonces usted ha encontrado el mayor factor primordial!

Una descripción detallada Algoritmo:

Puede hacerlo manteniendo tres variables:

El número que intenta factorizar (A) Una tienda divisor de corriente (B) Una tienda de mayor divisor (C)

En un principio, sea (A) sea el número que está interesado en - en este caso, es 600851475143. A continuación, vamos (B) sea 2. Tener un condicional que comprueba si (A) es divisible por (B). Si es divisible, dividir (A) (B), reset (B) a 2, y volver a comprobar si (a) es divisible por (B). Si no, si (a) no es divisible por (B), incremento (B) por 1 y luego comprobar si (A) es divisible por (B). Ejecutar el bucle hasta que (A) es 1. El (3) regrese será el mayor divisor primo de 600,851,475,143.

Hay muchas maneras que usted podría hacer esto más eficaz - en lugar de incrementar al siguiente número entero, se podía incremento para el siguiente entero necesariamente mejor momento, y en lugar de mantener una mayor tienda divisor, sólo podría devolver el número actual cuando su Sólo divisor es en sí. Sin embargo, el algoritmo he descrito anteriormente se ejecutará en segundo independientemente.

La implementación en Python es el siguiente: - 

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Ejemplo: Vamos a encontrar el mayor factor primordial de 105 usando el método descrito anteriormente

.

Sea (A) = 105. (B) = 2 (que siempre comenzar con 2), y que no tienen un valor para (C) todavía.

es (a) divisible por (B)? Nº Incremento (B) por 1: (B) = 3. Es es (a) divisible por (B)? Si. (105/3 = 35). El divisor más grande encontrado hasta ahora es 3. Sea (C) = 3. Actualización (A) = 35. Reset (B) = 2.

Ahora, es (A) divisible por (B)? Nº Incremento (B) por 1: (B) = 3. ¿Es (A) divisible por (B)? Nº Incremento (B) por 1: (B) = 4. ¿Es (A) divisible por (B)? Nº Incremento (B) por 1: (B) = 5. ¿Es (A) divisible por (B)? Si. (35/5 = 7). El divisor más grande que encontramos previamente se almacena en (C). (C) es actualmente 3. 5 es mayor que 3, por lo que la actualización (C) = 5. Actualización (A) = 7. Nos RESET (B) = 2.

A continuación, repetimos el proceso para (A), pero sólo mantendrán a incrementar (B) hasta (B) = (A), ya que 7 es primo y no tiene divisores distintos de uno mismo y 1. (Ya podíamos parar cuando (B)> ((a) / 2), ya que no se puede tener divisores de números enteros mayores que la mitad de un número - el divisor más pequeño posible (que no sea 1) de cualquier número es 2)

Así que en ese momento nos volvemos (A) = 7.

Trate de hacer algunos de estos a mano, y obtendrá la caída de la idea

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top