Program to factorize a number into two smaller prime numbers

Question

I have a very big number, and I want to make a program, that finds two prime numbers, that will give the original number, if multiplied.

Ex.
Original_number = 299

// The program should get these two numbers:

q = 13
p = 23

The program runs fine at the start, but at a certain point, it just stops, and I'm not sure what is wrong. The code:

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()

I have written the program in python, and I know it probably isn't good, because I'm new to python.(I have been programming C++, and I'm not even good at it) But I hope you can help me find the problem :)

ps. What is the maximum size of the original number? How many ciphers can it have?

Answer 1

A simple approach is trial division:

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

Then factors(299) returns [(13,23)]

There are problems with this method for large numbers:

1. Large numbers may exceed the python integer limit (found in sys.maxint). A 64-bit machine will be limited to 18 decimal digits.

2. Factoring large numbers is a hard problem, and an open research question. Trial division is about as brute force as it comes, but it will work for smaller numbers. Otherwise, you'll quickly need a more sophisticated algorithm. See wikipedia for a discussion.

3. If you're going to brute-force numerical problems, python is the wrong language. Identical algorithms will run faster in a compiled language like C++.