6

実際、N a (おそらく非常に大きい) 偶数整数が与えられた場合、gcd(F,R) = 1、F>R、および F が可能な限り小さい N = F * R を見つけたいと思います (完全にファクタリング F)。問題の核心は、R < sqrt(N) となる最大の除数 R を見つけることです。

たとえば、N=36 の場合、F=9 と R=4 になります。R は必ずしも素数または素数ベキではないことに注意してください。N を因数分解していないことに注意してください。F と R の唯一の制限は、それらが互いに素であることです。

これは私の簡単で素朴なバージョンで、動作しています:

def factor_partial(N):
    for R in xrange(int(math.sqrt(N)),1,-1):
        if N%R == 0 and gcd(R,N/R) == 1:
            return N/R, R

私が想像するもう 1 つの方法は、除数を昇順で見つけ、途中で非除数の倍数を削除することです。何かのようなもの：

def factor_partial(N):
    i = range(2, int(sqrt(N)) + 1)
    while i:
        if N % i[0] != 0:
            remove_multiples(i, i[0]) #without removing i[0]
        else:
            if gcd(i[0], N/i[0]) == 1:
                R = i[0]
        i.pop(0) #remove i[0]

    return N/R, R

これは遅く、メモリを大量に消費すると思いますが、i代わりにジェネレーターを使用すると効率的になる可能性があります。発電機はあまり使っていません。

最初のバージョンを改善できますか? 2 番目のバージョンは実行可能ですか (どうすればよいですか)? より良い完全に異なる方法はありますか？

Python、C、または疑似コードで答えを探しています。

これは、数論のクラスのプロジェクトです。Pocklingtonに基づく素数性テストを実装しています。因数分解アルゴリズムが必要ですが、私たちは何も研究していません。おそらく、クラスの範囲外にある二次ふるいなどを使用するつもりはありません。提起された質問に関する具体的なヘルプを探しています。

4

3 に答える 3

5

ウィキペディアには素因数分解アルゴリズムの素晴らしいリストがあります：http： //en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

2番目のアプローチは、ふるいを効果的に使用し、Nがいくつかの小さな素数の倍数である場合に問題をすばやく減らすという優れた特性を備えています。2..sqrt（n）のすべての可能な除数ではなく、素数をループすることにより、コードを改善できます。

また、追加の作業を行う前にNが複合であることを確認するために、素数性テストから始めることもできます。

あなたのメモはあなたがNを因数分解していないと言っていますが、問題は関連しています。FとRの検索は、 Nの素因数の重複しない組み合わせを探索することになります。

の場合、NN==36の素因数分解はです。FとRの因数には、それらすべてが含まれている必要があり（したがって）、重複することはできません（したがって）。したがって、4と9はすぐに現れます。2, 2, 3, 3F*R==NGCD(F,R)==1

より有益な例はですN==23256。その因数分解は2,2,2,3,3,17,19です。FとRの間にオーバーラップはあり得ないため、各プライムベースは2つのバケットのうちの1つにしか入ることができません（つまり、2つすべてを取得するか、いずれも取得しません）。したがって、因子をにグループ化でき8,9,17,19ます。Rを見つけるには、可能な限り大きく、23256の平方根である152.49未満の因子の組み合わせが必要です。選択肢は、{8}、{9}、{8,9}、{8,17}です。 、{8,19}。それらの最大のもの8*19は152です。対応するFは17*19または153です。

上記の選択肢は、として計算され[choice for choice in powerset([8,9,17,19]) if prod(choice) < math.sqrt(N)]ます。

したがって、プログラム全体はほぼこれに要約されます。

prime_factors = factorize(N)      # [2,2,2,3,3,17,19]
clusters = [p**e for p, e in collections.Counter(prime_factors).items()]  # [8,9,17,19]
R = max(prod(group) for group in powerset(clusters) if prod(group) < math.sqrt(N))
F = N // R

べき集合の検索は、集合がNの平方根を超えるたびに集合の生成を取り除くことにより、より高速に行うことができます。

因数分解は計算コストが高く、べき集合は非常に速く成長しますが、 Nの平方根から始まり、下に向かって多くの除算を行う元のアルゴリズムを開始するよりもはるかに少ない作業である可能性が高いことに注意してください。

于 2011-11-25T18:29:32.747 に答える
0

N の素因数分解を取得して、sqrt(N) より小さいすべての素因数の最大の積の組み合わせを見つけることができますか?

たとえば、36 の場合、素因数分解は 2*2*3*3 であることがわかります。次に、素数のさまざまな組み合わせをすべて試します。

2 = 2
3 = 3
2*2 = 4
2*3 = 6
3*3 = 9
2*2*3 = 12
2*3*3 = 18
2*2*3*3 = 36

そして、これらはすべて 36 の因数であることを知っているので、最大のものを見つけて sqrt(36) より小さくなり、4 になります。

ただし、素数または素因数分解の既存のリスト、またはいくつかの素晴らしい素因数分解アルゴリズムを既に取得していない限り、またはすべてを実行していない限り、最初のバージョンを実行するよりもはるかに高速になる方法は実際にはわかりませんこれは非常に大きな数です。

しかし、それでも (最初のバージョンの絶賛に戻って) O(sqrt(n)) は非常に高速なランタイムであり、O(1) メモリしか必要としないため、実際には最初のアルゴリズムが最適な方法である可能性があります。特に最近のコンピューターの C では、どのように遅くなるかわかりません。

于 2011-11-25T19:44:35.307 に答える
0 
def factor_partial(N):
    R = int(sqrt(float(N)))
    sieve = [1, 1] + [0] * (R-1)
    for i in xrange(2, R) :
        if sieve[i]==0 :
            j=i*i;
            while j<=R :
                sieve[j]=1
                j = j + i
    primes = [i for i in xrange(R+1) if sieve[i]==0]

    saveN = N
    primepower_divisors = []
    for i in primes :
        if N%i == 0 :
            term = 1
            while N%i == 0 :
                term = term * i
                N = N / i
            primepower_divisors = primepower_divisors + [term]
            if N==1 : break

    largecoprime_divisors = [1]
    for i in primepower_divisors :
        for j in largecoprime_divisors :
            largecoprime_divisors = largecoprime_divisors + [i*j]

    F = min([i for i in largecoprime_divisors if i>R])
    return F, saveN/F

ふるい法を使用して素数のリストを計算しました (素数のリストの計算には多くの最適化が可能です) F%p == 0 および R%p のような素数 p が存在しないという事実を使用できます。 == 0 。gcd(F, R)=1 なので

于 2011-11-25T19:45:29.017 に答える