将一个数字分解为两个较小的质数的程序

Question

我有一个非常大的数字，我想写一个程序，找到两个质数，它们相乘可以得到这个原始数字。

Ex.
Original_number = 299

// The program should get these two numbers:

q = 13
p = 23

程序一开始运行得很好，但到了一定的时刻，它就停止了，我不太确定哪里出了问题。代码如下：

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

我用Python写了这个程序，我知道它可能写得不好，因为我刚开始学Python。（我之前学的是C++，而且我连C++也没学得很好）但我希望你们能帮我找出问题所在 :)

另外，原始数字的最大大小是多少？它可以有多少位数？

Answer 1

除了Jochel Ritzel和DSM的回答之外，main()函数中的while循环逻辑没有考虑到一些情况，比如当数字不是两个质数的乘积时，这样就会导致程序进入无限循环。

另外，如果你想要分解非常大的数字（比如超过20到30位的数字），你现在的方法可能会太慢。为了得到比较好的结果，你至少应该使用埃拉托斯特尼筛法，提前生成一个足够大的质数列表。

确实有一些比较复杂的算法可以处理更大的情况，但总的来说，这个问题比较难，解决方案在数字位数增加时会变得非常不稳定。

Answer 2

首先，把一个数字进行因式分解。你会得到一组质因数。如果这个列表里正好有两个数字，而且这两个数字符合你的需求，那就成功了。如果不行，就换一个数字试试。

不过，上面的方法其实有点浪费时间。我更喜欢先准备一份质数的列表，然后生成所有可能的两个质数的组合，再把它们相乘。这样得到的结果就是只能被两个质数分解的数字。就像这样：

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]

Answer 3

一种简单的方法是试除法：

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

然后 factors(299) 会返回 [(13,23)]

不过，这种方法在处理大数字时会有一些问题：

1. 大数字可能会超过 Python 的整数限制（可以在 sys.maxint 中找到）。在 64 位的机器上，数字最多只能有 18 位。

2. 对大数字进行因数分解是个难题，目前还没有解决方案。试除法算是最简单粗暴的方法，但它适合小数字。如果数字太大，你就需要用更复杂的算法了。想了解更多，可以查看 维基百科 的讨论。

3. 如果你打算用暴力破解的方法解决数字问题，Python 可能不是最佳选择。相同的算法在像 C++ 这样的编译语言中运行会更快。