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

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++，而且我什至不擅长） 但我希望你能帮我找到问题:)

ps。原始数字的最大尺寸是多少？它可以有多少个密码？

Answer 1

只需对一个数字进行因式分解即可。您将获得主要因素列表。如果该列表恰好包含两个数字，并且这些数字适合您的目的，那么您就赢了。否则尝试另一个号码。

但是上面的做法是相当浪费的。我宁愿获取一个素数列表，生成它的所有对并相乘。结果将是一个只能因式分解为 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 2

一个简单的方法是试除：

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. 对大数进行因式分解是一个难题，也是一个开放的研究问题。试除法几乎是蛮力的，但它适用于较小的数字。否则，您很快就会需要更复杂的算法。请参阅wikipedia进行讨论。

3. 如果您要暴力破解数值问题，Python 是错误的语言。相同的算法在 C++ 等编译语言中运行得更快。

Answer 3

isPrime

错了。当数字不是质数时，返回 1。而且你从来没有测试过这个数字是否可以除以 2。我没有再进一步看。

专业提示：Python 不是 C。有

True, False

，并且不需要

if,  while

中的所有括号。

您应该真正测试您编写的每个函数，而不是整个程序 - 这不会告诉您错误在哪里。

Answer 4

除了 Jochel Ritzel 和 DSM 的答案之外，main() while 循环中的逻辑无法考虑数字不是两个素数的乘积的情况（然后它将进入无限循环）。

此外，如果您希望对非常大的数字（例如超过 20-30 位数字）进行因式分解，那么您的方法可能太慢了。如果您想获得可接受的结果，您应该至少使用埃拉斯托尼筛提前生成足够大的素数列表。

有（相当复杂的）算法可以处理更大的情况，但总的来说，这是一个困难的问题，并且它的解决方案随着位数的扩展非常糟糕。

Answer 5

按照以下逻辑：

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

如果 i 是奇数并且素数不能被它整除，它将永远循环，并且在这里卡在 3 上。[另一个明显的问题已经指出了。]

Answer 6

修改了 Chris P. 的方法：

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

现在可以正确处理平方数。