4

この関数を作成して使用して、数値の素因数を生成します。

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 が素因数に対して生成するものと一致します。(そして最大のものは Project Euler #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を大きな数の素因数として計算できるようにコードを変更する簡単な方法はありますか?

（私はこれの生のコードまたはアルゴリズムに興味があります-私のためにそれを行うライブラリへのポインタではありません、ありがとう！）

4

3 に答える 3

8

これを行う従来の方法は、各素因数を順番に分割してから、因数分解方法を繰り返すことです。これは、実際に数を分割する（少数の）素数のみを気にするため、一般に、すべての素数をふるいにかけるよりも高速です。

もちろん、試行除算よりも優れた素因数分解アルゴリズムはたくさんあります。人々は通常、二次ふるい法のようなものを広範囲の数に使用し、ポラードのロー法を小さい方に、数体ふるい法を大きい方に使用します。これらはすべて非常に複雑です。

事前にすべての素数をふるいにかけているので、アルゴリズムの効率を気にする必要はありません。それを考えると、事後法で多重度を計算するのが最も簡単です。これは@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)]
于 2012-09-04T18:10:40.200 に答える
4

明確な素因数を取得したら、次のようなことができます。

factors = []
for f in distinct_prime_factors:
    while n % f == 0:
        factors.append(f)
        n /= f

factorsすべての素因数のリストを保持します。

于 2012-09-04T18:04:17.827 に答える
2

敬意を表して、これは次の方法でより簡単になります (そして、はるかに高速で効率的です)。

from collections import defaultdict
from math import sqrt

def factor(n):
    i = 2
    limit = sqrt(n)    
    while i <= limit:
      if n % i == 0:
        yield i
        n = n / i
        limit = sqrt(n)   
      else:
        i += 1
    if n > 1:
        yield n

def pfac(num):
    d=defaultdict(int)
    for f in factor(num):
        d[f]+=1

    terms=[]
    for e in sorted(d.keys()):
        if d[e]>1:
            terms.append('{:,}^{}'.format(e,d[e]))
        else:
            terms.append('{:,}'.format(e))

    print ' * '.join(terms),'=','{:,}'.format(num)           

pfac(600851475143*1000000-1)
pfac(600851475143*1000000)
pfac(600851475143*1000000+1)

版画:

83 * 127 * 57,001,373,222,939 = 600,851,475,142,999,999
2^6 * 5^6 * 71 * 839 * 1,471 * 6,857 = 600,851,475,143,000,000
3^2 * 19 * 103 * 197 * 277 * 16,111 * 38,803 = 600,851,475,143,000,001
于 2012-09-05T00:40:48.213 に答える