在Python中对一个数字进行分解

Question

这是我的代码:

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.正如你所看到的,它首先制作一个Eratosthenes筛子n,然后使用列表理解来返回筛子中所有值的因子n.它为此目的工作得相对较好,但是,我希望它返回一个列表,这样如果你将其中的每个项目相乘,结果就是n.你明白了吗？

例如,factorize(99020)返回[2, 5, 4951],但我希望它返回[2, 2, 5, 4951],如2*2*5*4951 = 99020.

我知道我的方法甚至不是很接近,但你能帮助我做到这一点吗？

Answer 1

Blender的答案中的代码非常好,但是这个算法缺乏一个非常重要的方面:它测试的方式太多了.例如,尝试分解n=392798360393,这是一个素数,它会尝试将它除以它下面的所有数字(包括它自己).这将花费很多时间.

真的有必要吗？如果n == a*b和a < b,已经发现a,我们并不真正需要测试分n通过b.我们知道它太划分了n,因为n/a == b暗示n/b == a.所以我们只需要测试潜在因子a小于(或等于)潜在因素b.也就是说,直到达到该数字的平方根.

此外,不是从每个减少2开始,而是n可以从之前的值开始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秒.

这保证只生成素数(因为我们将找到的每个因子分开,我们以非递减顺序尝试候选者).如果我们同时考虑几个数字,那么首先生成素数然后仅通过素数进行测试(通过所有数字进行测试,如上所述)的开销将是值得的.因为只考虑一个数字,它可能是不值得的,这取决于你的黄金代的速度.

但是,当一次分解几个数字时,真正应该做的是首先创建最小因子筛,我们用给定范围内的每个数字标记其最小(素数)因子(由筛子生成)来代替只是在Eratosthenes的筛子中True或者False在Eratosthenes的筛子中.然后使用这个最小因子筛来对每个给定的数字进行有效因子分解,在相同的范围内,通过它们的因子连续除以最小值,这可以通过筛子中的直接查找而不是测试来有效地找到.重新:

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))

Answer 2

Eratosthenes的Sieve帮助您找到低于特定限制的素数.找到特定数字的因素并不能帮助您.

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

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