Program to factorize a number into two smaller prime numbers

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

    Elap开发者_如何学PythonsedTime = 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?

---

Just factorize a number. You'll get a list of prime factors. If the list contains exactly two numbers, and the numbers are good for your purposes, you won. Else try another number.

But the approach above is quite wasteful. I'd rather take a list of primes, generate all pairs of it and multiply. The result would be a list of numbers that, well, can only be factorized into 2 primes. Like this:

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]

---

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++.

---

isPrime is wrong. You return 1 when the number is not prime. Also you never test if the number can be divided by 2. I didn't look any further than that.

Protip: Python is not C. There is True, False and you don't need all the brackets in if, while.

You should really test every function you write, not the whole program - that tells you nothing about where the bugs are.

---

In addition to Jochel Ritzel's and DSM's answers, the logic in main() while loop fails to account for cases when the number is not a product of two primes (then it will go into infinite loop).

Also, if you expect to factor really large numbers (say more than 20-30 digits), your approach is probably too slow. You should use Erastothenes sieve at minimum to generate a large enough list of primes in advance if you want to get acceptable results.

There are (pretty sophisticated) algoritms to deal with larger cases, but in general, this is a difficult problem and the solution to it scales very badly with number of digits.

---

In the following logic:

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

If i is odd and prime isn't divisible by it, it'll loop forever, and here it gets stuck on 3. [The other obvious problem has already been pointed out.]