Tengo un número muy grande y quiero hacer un programa que encuentre dos números primos, que darán el número original, si se multiplica.

Ex.
Original_number = 299

// The program should get these two numbers:

q = 13
p = 23

El programa funciona bien al principio, pero en cierto punto, simplemente se detiene, y no estoy seguro de qué está mal. El código:

import time
import math

def main():
    time1 = time.clock()
    q  = int(0)
    p = int(0)
    finalnumber = int(377)


    print("in main \n")
    print("q = ", q)
    print("\n p = ", p)

    gotResult = 0

    while(gotResult == 0):

        p = GetNextPrime(p)

        if(p >= finalnumber):
            q = GetNextPrime(q)
            p = q
            p = GetNextPrime(p)

        if(q * p == finalnumber):
            gotResult == 1
            break

    print("q = ", q)
    print("\n p = ", p)
    time2 = time.clock()

    ElapsedTime = time2 - time1
    print("Elapsed time: ", ElapsedTime)


def GetNextPrime(prime):
    print("in GetNextPrime \n")
    isPrime = 0

    while(isPrime == 0):
        prime = prime + 1
        if(IsPrime(prime)== 1):
            isPrime = 1

    return prime

def IsPrime(prime):
    print("in IsPrime \n")
    isPrime = 0
    i = 2

    while(i <= math.sqrt(prime)):
        if(i % 2 == 0):
            i = i+1
        if(prime % i == 0):
            isPrime = 1
            break


    return isPrime

#start of program here
main()

He escrito el programa en Python, y sé que probablemente no sea bueno, porque soy nuevo en Python (he estado programando C ++, y ni siquiera soy bueno en eso). Pero espero que me puedan ayudar. encuentra el problema :)

PD. ¿Cuál es el tamaño máximo del número original? ¿Cuántas cifras puede tener?

1
Janman 6 jun. 2011 a las 19:08

5 respuestas

La mejor respuesta

Un enfoque simple es la división de prueba:

import math
def factors(number):
    return [(x, number / x)  for x in range(int(math.sqrt(number)))[2:] if not number % x]

Entonces factors(299) devuelve [(13,23)]

Hay problemas con este método para grandes números:

  1. Los números grandes pueden exceder el límite entero de Python (que se encuentra en sys.maxint). Una máquina de 64 bits estará limitada a 18 dígitos decimales.

  2. Factorizar números grandes es un problema difícil y una pregunta de investigación abierta. La división de prueba tiene casi la misma fuerza bruta, pero funcionará para números más pequeños. De lo contrario, necesitará rápidamente un algoritmo más sofisticado. Vea wikipedia para una discusión.

  3. Si vas a tener problemas numéricos de fuerza bruta, Python es el lenguaje incorrecto. Los algoritmos idénticos se ejecutarán más rápido en un lenguaje compilado como C ++.

2
Chris P 6 jun. 2011 a las 22:14

En la siguiente lógica:

while(i <= math.sqrt(prime)):
    if(i % 2 == 0):
        i = i+1
    if(prime % i == 0):
        isPrime = 1
        break

Si soy impar y primo no es divisible por él, se repetirá para siempre, y aquí se queda atascado en 3. [El otro problema obvio ya se ha señalado].

0
DSM 6 jun. 2011 a las 15:22

Solo factoriza un número. Obtendrá una lista de factores primos. Si la lista contiene exactamente dos números, y los números son buenos para sus propósitos, ganó. De lo contrario, intente con otro número.

Pero el enfoque anterior es bastante derrochador. Prefiero tomar una lista de números primos, generar todos los pares y multiplicar. El resultado sería una lista de números que, bueno, solo se pueden factorizar en 2 primos. Me gusta esto:

some_primes = [2, 3, 5, 7, 11] # you can generate a better list
my_numbers = [x*y for x in some_primes for y in some_primes]
3
9000 6 jun. 2011 a las 15:15

isPrime está mal. Devuelve 1 cuando el número es no primo. Además, nunca se prueba si el número se puede dividir por 2. No busqué más allá de eso.

Protip: Python no es C. Hay True, False y no necesitas todos los corchetes en if, while.

Realmente deberías probar cada función que escribes, no todo el programa, eso no te dice nada sobre dónde están los errores.

1
Jochen Ritzel 6 jun. 2011 a las 15:22

Además de las respuestas de Jochel Ritzel y DSM, la lógica en main () while loop no tiene en cuenta los casos en que el número no es producto de dos números primos (luego irá a bucle infinito).

Además, si espera factorizar números realmente grandes (digamos más de 20-30 dígitos), su enfoque probablemente sea demasiado lento. Debe usar el tamiz Erastothenes como mínimo para generar una lista lo suficientemente grande de primos por adelantado si desea obtener resultados aceptables.

Hay algoritmos (bastante sofisticados) para tratar casos grandes, pero en general, este es un problema difícil y la solución a este se escala muy mal con el número de dígitos.

1
J S 6 jun. 2011 a las 15:27