较大数的非不同质因数

我编写并使用这个函数来生成数字的质因数：

import numpy as np
from math import sqrt

def primesfrom3to(n):
    """ Returns a array of primes, p < n """
    assert n>=2
    sieve = np.ones(n/2, dtype=np.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = False
    return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]    

def primefactors(tgt,verbose=True):
    if verbose: 
        print '\n\nFinding prime factors of: {:,}'.format(tgt)

    primes=primesfrom3to(sqrt(tgt)+1)

    if verbose:
        print ('{:,} primes between 2 and square root of tgt ({:.4})'.
                      format(len(primes),sqrt(tgt))) 

    return [prime for prime in primes if not tgt%prime]

如果我用以下值来调用它欧拉计划 #3 http://projecteuler.net/problem=3，它成功地生成了不同素数的列表：

>>> print primefactors(600851475143)
Finding prime factors of: 600,851,475,143
62,113 primes between 2 and square root of tgt (7.751e+05)
[71, 839, 1471, 6857]

这符合什么Wolfram Alpha 生产 http://www.wolframalpha.com/input/?i=600851475143%20prime%20factors为主要因素。 （最大的是欧拉计划 #3 的正确答案）

现在假设我想要该数字 x 1e6 的因数：

>>> print primefactors(600851475143*1000000)
Finding prime factors of: 600,851,475,143,000,000
39,932,602 primes between 2 and square root of tgt (7.751e+08)
[2, 5, 71, 839, 1471, 6857]

对于这个更大的数字，Wolfram Alpha 生产 http://www.wolframalpha.com/input/?i=600851475143000000%20prime%20factors:

2**6 * 5**6 * 71 * 839 * 1471 * 6857

有没有一种简单的方法来修改我的代码，我可以计算出2和5作为较大数的质因数？

（我对它的原始代码或算法感兴趣——而不是指向能为我做这件事的库的指针，谢谢！）

传统的方法是依次除掉每个质因数，然后递归分解因式分解方法。一般来说，这比筛选所有素数要快，因为您只关心实际除以您的数字的（少数）素数。

当然，有很多很多比试除法更好的素因数分解算法；人们通常对大范围的数字使用二次筛之类的东西，在小端使用 Pollard 的 rho 方法，在大端使用数域筛。这些都是显著地更复杂。

由于您事先筛选了所有素数，因此您并不关心算法的效率。鉴于此，最简单的方法就是计算出多重性事后，这是 @tobias_k 所写的。您也可以将其分解为一个单独的函数，如下所示

def multiplicity(n, p):
    i = 0
    while not n % p:
        i, n = i+1, n/p
    return i

and then

>>> n = 600,851,475,143,000,000
>>> n = 600851475143000000
>>> factors = [2, 5, 71, 839, 1471, 6857]
>>> [(f, multiplicity(n,f)) for f in factors]
[(2, 6), (5, 6), (71, 1), (839, 1), (1471, 1), (6857, 1)]