数字较大的非明显素因子

Question

我编写并使用此函数来生成数字的素数因子:

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]

如果我使用Project Euler#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为主要因素产生的结果一致.(最大的项目欧拉#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产生:

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

有一种简单的方法来修改我的代码,我可以计算的幅度2和5更大数量的首相因素是什么？

(我对这个原始代码或算法很感兴趣 - 不是指向我这样做的库的指针,谢谢!)

Answer 1

传统的方法是依次分出每个素数因子,然后依据你的因子分解方法.这通常比筛选所有素数更快,因为你只关心实际划分数量的(少数)素数.

当然,有许多更好的素数因子分解算法比试验分割更好; 人们通常使用类似二次筛的东西用于各种数字,Pollard的rho方法在小端,数字字段在大的筛子上.这些都是显著更加复杂.

由于您事先正在筛选所有质数,因此您不关心算法的效率.鉴于此,最简单的事情就是事后计算多重性,这就是@tobias_k写的.您也可以将其分解为单独的函数

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

然后

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