list之最大的质因数 Python

yxwkf 阅读:11 2024-05-29 10:23:45 评论:0

我正在尝试使用 Python 找到给定数字 (600851475143) 的最大质因数。我已经编写了以下代码,但问题是,它需要永远,可能是因为它在列表中迭代了数百万次。如何优化这个过程?

def factors(n): 
    list = [] 
    i = 1 
    while i < n: 
        if n % i == 0: 
            list.append(i) 
        i += 1 
    return list 
 
def prime(n): 
    list = factors(n) 
    primelist = [] 
    for item in list[1:]: 
        if item % 2 != 0 and item % 3 != 0 and item % 4 != 0 and item  \ 
        % 5 != 0 and item % 6 != 0 and item % 7 != 0 and item % 8 != 0 \ 
        and item % 9 != 0: 
            primelist.append(item) 
    return primelist 
 
def greatestprime(n): 
    list = prime(n) 
    list[0] = lnum 
    i = 1 
    while i < len(list): 
        if list[i] > lnum: 
            lnum = list[i] 
    return lnum 
 
#print(greatestprime(600851475143)) 

请您参考如下方法:

如果您只是对单个数字 n 进行因式分解,那么测试从 2 到 sqrt(n)(n 的平方根)的每个数字的天真方法应该可以快速得出最大为 1014 的数字的结果。您正在编写不必要的代码。

稍微好一点的方法是:

  • 测试 2,然后测试每个奇数
  • 测试 2、3、5,然后测试所有形式为 6k + 1 和 6k + 5 的整数,其中 k >= 1
  • 上述两种方法是 wheel factorization,分别为 n = 2 和 n = 2*3 = 6。您可以将其提高到 n = 2*3*5*7 = 210(更高不会带来太多效率)。

  • 稍微好一点的方法是通过 Eratosthenes 筛和测试(无冗余测试)生成素数。还有更好的方法,例如 Pollard's rho 因式分解,但除非您处理更多数字,否则这两种方法都有些矫枉过正。


    标签:Python
    声明

    1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

    关注我们

    一个IT知识分享的公众号