logo标签列表

在 Python 中分解一个数字

pythonloopsprimesprime-factoringsieve-of-eratosthenes
9
以下是我的代码：
def factorize(n):
    sieve = [True] * (n + 1)

    for x in range(2, int(len(sieve) ** 0.5) + 1):
        if sieve[x]: 
            for i in range(x + x, len(sieve), x):
                sieve[i] = False

    lowerPrimes = i for i in range(2, len(sieve)) if sieve[i]] and (n % i == 0)]
    return lowerPrimes
factorize(n)函数返回给定值n的所有质因数。可以看到，它首先为n创建一个埃拉托色尼筛，然后使用列表推导式来返回筛中的所有是n的因数的值。对于这个目的，它运行得相当好，但我希望它返回一个列表，以便如果你将其中的每个项相乘，结果就是n。你了解我的意思吗？
例如，factorize(99020)返回[2, 5, 4951]，但我想让它返回[2, 2, 5, 4951]，因为2*2*5*4951 = 99020。
我知道我的方法根本不接近，但你能帮我改进一下吗？
这段代码由于多个问题而无法运行 - 其中一个是缩进，但更重要的是在返回之前的最后一行存在语法错误。 - Burhan Khalid
5个回答
18

Blender的回答中的代码非常好，但是这个算法在一个非常重要的方面上缺乏测试。例如，尝试分解 n=392798360393，它是一个质数，它将尝试将其除以所有小于它的数字（包括自己）。这需要很多时间。

这真的有必要吗？如果 n==a*b 并且 a < b，在找到 a 后，我们不需要真的去测试是否可以整除 n 与 b。因为我们知道它也能整除 n，因为 n/a==b 意味着 n/b==a。所以我们只需要在潜在的因子 a 小于（或等于）潜在的因子 b 时进行测试。也就是说，直到达到该数字的平方根。

另外，无需为每个减小的n 重新从2开始，可以从上一个值的i 开始：

from math import sqrt
def factors(n):    # (cf. https://stackoverflow.com/a/15703327/849891)
    j = 2
    while n > 1:
        for i in range(j, int(sqrt(n+0.05)) + 1):
            if n % i == 0:
                n //= i ; j = i
                yield i
                break
        else:
            if n > 1:
                yield n; break

事实上，用这段代码对9000009进行因数分解只需要0.08秒，在Ideone上，而不是0.59秒。

这个方法保证只能得到质数（因为我们每次都除尽一个因子，并按照非递减的顺序尝试候选数）。如果我们要同时对多个数进行因数分解，先生成质数列表再只使用这些质数来测试（而不是类似前面所做的测试所有的数），会值得这个额外开销；但如果只是对一个数进行因数分解，在速度和质数生成的效率之间取舍就有点难了。

然而，当同时对多个数进行因数分解时，更好的方法是首先创建最小因子筛（smallest factor sieve），在给定范围内通过标记每个数字的最小（质）因数（从该筛子生成的因子中获取），而不是像Eratosthenes筛法中那样仅用True或False来标记。然后，我们可以通过直接在筛子中查找而不是重新测试来高效地对每个数字进行因数分解，从最小的因子开始，一直到这个数的因子，这些因子在筛子中可以以高效的方式直接查找：

def sfs_factorize(nums):
    top = max(nums)
    sv = smallest_factor_sieve(top)
    for k in nums:
        fs = [] ; n = k
        while n > 1:
            f = sv[n]    # no testing
            n //= f
            fs.append(f)
        print( k, list(fs))
1
哇，太棒了。谢谢。 - Juan José Castro
10
埃拉托斯特尼筛法可以帮助您找到小于某个限制的质数。但它并不能帮助您找到特定数字的因子。
如果您想要做到这一点，我能想到的最简单的方法是像下面这样：
def factors(n):
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                n //= i
                yield i
                break

for factor in factors(360):
    print factor

这基本上是找到n的最小因子（保证为质数），将n除以该数字并重复此过程，直到n等于1。 输出为：
2
2
2
3
3
5

他们相乘得到原始数字：
>>> from operator import mul
>>> reduce(mul, factors(360))
360
1
你的方法非常直接，比我预期的任何东西都要干净得多。对于一个初学者程序员有什么建议吗？ - Juan José Castro
@user2278662：我不是专家，但我的唯一建议是去创造东西。 - Blender
@Jared：我在追求简单，但你可能是对的。我不确定生成质数的开销是否值得。 - Blender
素数或非素数与此代码进行的大量无用测试相比微不足道。更多信息请参见我的答案。 - Will Ness
@WillNess：正如我之前所说，我的代码并不是为了效率而设计的。我尽可能地缩短了代码长度，以便为OP提供一些可用的东西。有更好的整数分解算法存在（请参见http://en.wikipedia.org/wiki/Integer_factorization#General-purpose），如果你想要高效地分解整数，为什么不使用其中之一呢？ - Blender
停留在sqrt上非常简单，通常只需要两行代码，并且带来巨大的好处。对我来说，编写GNFS要难得多，多得多。 :) - Will Ness
2

你的第一个筛质数的部分完全没问题。只有第二个找因子的部分需要改正。

在第二部分中，你应该除以质因数不止一次，而是多次，直到不能再被整除为止。这样可以确保考虑到所有质因数的幂次。

这个第二部分叫做用质数进行试除法。众所周知，只需要用小于Sqrt(N)的除数试除即可。剩下的N的值自然也会是质数。

对你的算法来说，还有一个非常重要的速度改进方法，就是将筛子大小设为Sqrt(N)，而不是N。因为我们只需要小于Sqrt(N)的质数。这是因为经过试除后，剩下的N自动成为了质数。

我还发现了一个改进你筛选部分的方法，你应该用for i in range(x * x, ...替换for i in range(x + x, ...。因为你可以根据埃拉托斯特尼筛法的经典算法，从x * x开始筛选，而不是从x + x开始。这将进一步提高速度。从x + x开始筛选也可以，但x * x将以更好的性能给出正确的结果。

另一个明显的改进是当你想要分解多个数字时，你可以多次重复使用筛子并扩展它，这将使代码更快。在重复使用筛子时，最好将得到的质数存储在单独的列表中，这样在第二次试除阶段，你不需要遍历整个筛子，而只需要遍历质数，这将再次加速。我没有在下面的代码中实现这两个改进，但如果你想要，我可以做到，只需告诉我。

完整的修正最终版本如下：

在线试用！

def factorize(n):
    sieve = [True] * int(n ** 0.5 + 2)
    
    for x in range(2, int(len(sieve) ** 0.5 + 2)):
        if not sieve[x]: 
            continue
        for i in range(x * x, len(sieve), x):
            sieve[i] = False

    factors = []
    for i in range(2, len(sieve)):
        if i * i > n:
            break
        if not sieve[i]:
            continue
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 1:
        factors.append(n)
    return factors

print(factorize(99020)) # [2, 2, 5, 4951]

输入：

99020

输出：

[2, 2, 5, 4951]

如果您只需要分解几个数字，使用试除法分解而不进行中间筛选阶段可能会更快。这也使代码更简单、更短。

以下是在没有筛选阶段的情况下执行分解的完整代码。

在此代码中，我通过仅尝试奇数除数来进行一项明显的速度改进，这将使总算法速度加倍。当然，在此之前，您需要分解出所有2的幂次方，我也已经做到了。

在线尝试！

def factorize(n):
    factors = []
    while (n & 1) == 0:
        factors.append(2)
        n >>= 1
    for d in range(3, 1 << 60, 2):
        if d * d > n:
            break
        while n % d == 0:
            factors.append(d)
            n //= d
    if n > 1:
        factors.append(n)
    return factors

print(factorize(99020)) # [2, 2, 5, 4951]
1

我不太熟悉这个问题是否应该被删除之类的，但无论如何我会帮忙。

我认为你已经正确使用了筛法部分。 关键是要使用while循环来重复除以一个有效的质因数。

factors = []
sieve[0] = sieve[1] = False # So I don't have to worry about trying to skip over these two
for testFactIndex, isPrime in enumerate(sieve):
    if isPrime:
        while n%testFactIndex == 0:
            n = n/testFactIndex
            factors.append(testFactIndex)
return factors
0

我的一行Python 3.8代码（使用赋值表达式）

f = lambda n: (p:=[next(i for i in range(2, n+1) if n % i == 0)] if n>1 else [])+(f(n//p[0]) if p else [])

Python中分解数字的详细视频

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接