7

这是我的代码：

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。

我知道我的方法还不够接近，但你能帮我做到吗？

4

5 回答 5

13

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

真的有必要吗？如果n == a*b并且a < b发现a我们真的不需要测试n除以b。我们知道它也分n，因为n/a == b暗示n/b == a。所以我们只需要在潜在因子a小于（或等于）潜在因子时进行测试b。也就是说，直到达到数字的平方根。

n此外，与其从 2 开始，不如从 2的前一个值开始i：

def factors(n):    # (cf. https://stackoverflow.com/a/15703327/849891)
    j = 2
    while n > 1:
        for i in xrange(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在 Ideone 上通过此代码进行分解需要 0.08 秒，而不是 0.59 秒。

这保证只产生素数（因为我们将找到的每个因子分开，并且我们以非递减的顺序尝试候选）。如果我们一次分解多个数字，那么首先生成素数然后仅通过素数进行测试（通过所有数字进行 aot 测试，如上所述）的开销将是值得的；只考虑一个数字可能不值得，这取决于您的素数生成的速度。

但是，当一次分解多个数字时，真正应该做的是首先创建最小的因子筛，我们在给定范围内用其最小（主要）因子（由筛生成它）来标记给定范围内的每个数字只是通过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))
于 2013-04-17T12:34:34.640 回答
8

埃拉托色尼筛法可帮助您找到低于特定限制的素数。它并不能真正帮助您找到特定数字的因数。

如果你想这样做，我能看到的最简单的方法是这样的：

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
于 2013-04-15T03:29:23.223 回答
1

你的第一个初筛部分完全没问题。只有第二因素发现部分应该被纠正。

在第二部分中，您应该除以素数，而不仅仅是一次，而是多次，直到它仍然可以整除。这将确保您考虑所有主要因素的权力。

第二部分称为素数试除法。众所周知，仅通过以下除数进行试除就足够了Sqrt(N)。N 的剩余值也将自动成为素数。

对您的算法的另一项非常重要的速度改进是它足以使筛子尺寸变大Sqrt(N)，而不是N。因为我们只需要小于 的素数Sqrt(N)。这是因为经过试除后剩余N的自动变成素数。

我还为您的筛分部分发现了一项改进，您应该替换for i in range(x + x, ...为for i in range(x * x, .... 因为你可以根据埃拉托色尼筛的经典算法，x + x而不是从开始筛分。这将进一步提高速度。从开始是可以的，但也会给出正确的结果和更好的性能。x * xx + xx * 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]

如果您只需要分解几个数字，那么在没有中间筛选阶段的情况下进行Trial Division Factorization可能会更快。这也使代码更简单、更短。

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

在这段代码中，我通过只尝试奇数除数做了一个明显的速度改进，这将使总算法速度加倍。当然，要做到这一点，您需要先排除 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]
于 2022-02-18T05:31:42.040 回答
0

我不太熟悉这个问题是否应该被删除或其他什么，但无论如何我都会提供帮助。

我认为你的筛子部分是正确的。关键是使用一个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
于 2013-04-15T03:29:03.323 回答
-1

我使用 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 中的因式分解数字

于 2020-10-19T18:51:09.350 回答