python - 仅使用数学库查找 n 因子的更快方法

Question

在将此标记为重复之前...

我需要找到 n 的所有因素（有很多解决方案）。我能够实现的最快的是通过循环 2 到 sqrt 的范围n。这是我迄今为止所拥有的......

def get_factors(n):
    factors = set()
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            factors.update([i, n // i])
    return factors

这是查找 的因素的一种非常快速的方法n，但我想知道是否有更快的方法来查找 的因素n。我唯一的限制是我只能在 Python 3.7 中使用数学库。关于如何更快地完成此操作的任何想法？我找不到只使用数学库的答案。我能做些什么来提高我当前算法的效率吗？

标签： pythonperformancemathpython-3.7factorization

Answer 1

编辑：就像@John Coleman 在此解决方案的评论中所说，最好在计算质数时获取因子，这样可以避免额外的工作，以防在筛子完成之前完成对数字的分解。更新后的代码将是：

def factors(number):
    n=int(number**.5)+1
    x=number
    divisors=[]
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            while x%p==0:
                x//=p
                divisors.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    if x!=1:
        divisors.append(x)    
    return divisors

OG解决方案：

使用Erathostenes Sieve获取 2 和 sqrt(n) 之间的质因数，然后检查哪些是 n 的除数。这将大大减少代码的运行时间。

Erathostenes 筛子只使用列表、操作%,>=,<=和布尔值。

这是一个比我分享给你的链接中的更短的实现：

def factors(number):
    n=int(number**.5)+1
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    divisors=[]
    x=number
    for i in primes:
        while x%i==0:
            x//=i
            divisors.append(i)
    if x!=1:
        divisors.append(x)    
    return divisors