为什么Python代码运行这么长时间，并且有什么方法可以快速获取输出？

Question

我有一个python代码来获得数字的最大素数，以下是我的代码 当我将数字输入到8位数字时需要几分钟，但是当我尝试以12位数字的代码600851475143运行代码时，它花了更多时间，但仍然没有给出任何输出或任何错误。 因此，有什么方法可以快速获取12位数字的输出？

def large_prime_fact(num):
    prime_factors=[]
    if num==2 or num==3:
        return(prime_factors.append(num))
    if num%2==0:
        prime_factors.append(2)
    for i in range(3,num,2):
        cnt=0
        if num%i==0:
            for j in range(2,i):
                if i%j==0:
                    cnt+=1
            if cnt==0 and i!=2:
                prime_factors.append(i)
    return prime_factors
if __name__=='__main__':
    number=int(input('Enter the number:'))
    print('The Largest prime factor for',number,'is :',max(large_prime_fact(number)))

Answer 1

正如Karl Knechtel指出的那样，您的方法严重缺陷。因此，您可能需要阅读很多有关质数和分解的问题。

就是说，这是我的解决方案。它可能仍会受益于进一步的优化，但它可以在约1毫秒中解决您的600851475143示例。

##define a prime numbers generator
def prime_gen():
    primes = []
    n = 2
    while n < 2**64:
        if primes == []:
            primes.append(n)
            yield n
        elif len(primes) == 1:
            n = 3
            primes.append(n)
            yield n
        else:
            n += 2
            limit = int(sqrt(n))+1
            for p in takewhile(lambda x:x<limit, primes):
                if n%p==0:
                    break
            else:
                primes.append(n)
                yield n

##factorize and return largest factor
def largest_prime(n):
    target = n
    for x in prime_gen():
        while target % x == 0:
            target //= x
            if target == 1:
                return x

Answer 2

您在这里有两种算法：

1. 用于查找num的所有因素的算法，其中包含
2. 一种用于检查您发现

这两个算法的每个因素的原始性的算法，以极高的效率实现。原始测试仪知道，从发现单个较小的值分开的那一刻起，它不是素数，但是您继续计数 all 是该数字的因素，并仅使用计数 /em>检查它是零还是非零。 Since the vast majority of composite numbers will have a smallish factor, you could just break your checking loop as soon as you find even one, knowing it's composite immediately and avoiding huge amounts工作。

Even better, you could pre-compute the prime numbers up to the square root of the target number (note: Only need to go up to the square root because any factor larger than the square root definitionally has a factor below the square root which you无需详尽的搜索即可找到它）。有效地计算固定范围内的所有质量数（尤其是目标数字的平方根（如1m以下），可以比重复的试用部更有效地完成 Eratosthenes的筛子是一种体面的小素数算法）。

用所有 aher 的廉价预定在平方根以下的质量因素（允许您便宜地确定平方根上方的任何主要因素）的廉价预定量应解决问题。还有其他优化，但这应该得到99％的优化。