4

これが私のコードですが、最適化したいと思います。nの平方根の前にすべての数値をテストするという考えは、多数の因子を見つけることに直面する可能性があることを考えると、好きではありません。 。あなたの答えは大いに役立つでしょう。前もって感謝します。

unsigned int* factor(unsigned int n)
{    
    unsigned int tab[40];
    int dim=0;
    for(int i=2;i<=(int)sqrt(n);++i)
    {
        while(n%i==0)
        {
            tab[dim++]=i;
            n/=i;
        }
    }
    if(n>1)
        tab[dim++]=n;
    return tab;
}
4

7 に答える 7

5

「適切な」c++でこれを行う方法に関する提案を次に示します（としてタグ付けされているため）。

PS。言及するのをほとんど忘れていました：私はsqrtawayへの呼び出しを最適化しました:)

http://liveworkspace.org/code/6e2fcc2f7956fafbf637b54be2db014aで実際にご覧ください

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

typedef unsigned int uint;

std::vector<uint> factor(uint n)
{    
    std::vector<uint> tab;

    int dim=0;
    for(unsigned long i=2;i*i <= n; ++i)
    {
        while(n%i==0)
        {
            tab.push_back(i);
            n/=i;
        }
    }
    if(n>1)
        tab.push_back(n);
    return tab;
}

void test(uint x)
{
    auto v = factor(x);
    std::cout << x << ":\t";
    std::copy(v.begin(), v.end(), std::ostream_iterator<uint>(std::cout, ";"));
    std::cout << std::endl;
}

int main(int argc, const char *argv[])
{
    test(1);
    test(2);
    test(4);
    test(43);
    test(47);
    test(9997);
}

出力

1:  
2:  2;
4:  2;2;
43: 43;
47: 47;
9997:   13;769;
于 2012-10-05T18:48:25.263 に答える
3

使用する場合

... i*i <= n; ...

i <= sqrt(n) よりもはるかに高速に実行される可能性があります

ところで、負の n の因数を処理するか、少なくとも負の数を渡さないようにする必要があります。

于 2012-10-05T18:42:45.713 に答える
3

実行時間をいくらか短縮する簡単な変更があります。すべての 2 を因数分解してから、奇数のみをチェックします。

于 2012-10-05T18:48:01.033 に答える
1

申し訳ありませんが、できません。多項式時間で大きな整数を因数分解できる既知の方法は地球上にありません。ただし、プログラムをわずかに (大幅にではなく) 高速化するのに役立つ方法がいくつかあります。ウィキペディアで参照先を検索してください。http://en.wikipedia.org/wiki/Integer_factorization

于 2012-10-05T18:38:39.880 に答える
1

あなたの解決策からわかるように、基本的にすべての素数（条件while (n%i == 0)）がそのように機能することがわかります。特に大きな数の場合、事前に素数を計算し、それらのみをチェックし続けることができます。素数の計算は、エラトステネスのふるい法またはその他の効率的な方法を使用して行うことができます。

于 2012-10-05T18:39:04.390 に答える
1 
unsigned int* factor(unsigned int n)

が典型的な 32 ビット タイプである場合unsigned int、数値が小さすぎて、より高度なアルゴリズムを実行できません。トライアル部門の通常の強化はもちろん価値があります。

Pete Becker で述べられているように、ループから除算を 2 で除算し、ループ内で奇数のみで除算する場合、基本的に、入力数値を因数分解するために必要な除算の数が半分になり、速度が向上します。関数はほぼ 2 倍になります。

これをさらに一歩進めて、ループ内の除数から 3 の倍数を取り除くと、除算の数が減るため、速度が 3 倍に近くなります (平均して、ほとんどの数値には大きな値はありません)。素因数ですが、2 または 3 で割り切れますが、これらの素因数分解の速度ははるかに小さくなりますが、これらの数は素因数分解が速くなります。素約数が大きい場合)。

// if your compiler doesn't transform that to bit-operations, do it yourself
while(n % 2 == 0) {
    tab[dim++] = 2;
    n /= 2;
}
while(n % 3 == 0) {
    tab[dim++] = 3;
    n /= 3;
}
for(int d = 5, s = 2; d*d <= n; d += s, s = 6-s) {
    while(n % d == 0) {
        tab[dim++] = d;
        n /= d;
    }
}

その関数を非常に頻繁に呼び出す場合は、65535 を超えない 6542 の素数を事前に計算し、それらを静的配列に格納し、素数のみで除算して、除数を見つけられないことがアプリオリに保証されているすべての除算を排除することをお勧めします。 .

unsigned intたまたま 32 ビットより大きい場合は、より高度なアルゴリズムの 1 つを使用すると有益です。小さな素因数を見つけるために試行分割から始める必要があります (小さな素因数が<= 1000、<= 10000、<= 100000またはおそらく<= 1000000テストする必要があるかどうかにかかわらず、私の直感では、小さな値の 1 つが平均的に優れていると思います)。試行分割フェーズの後、因数分解がまだ完了していない場合は、残りの因数が素数であるかどうかを確認します。たとえば、Miller-Rabin 検定の決定論的 (問題の範囲の) バリアントを使用します。そうでない場合は、お気に入りの高度なアルゴリズムを使用して要因を検索します。64 ビットの数値の場合、Pollard の rho アルゴリズムをお勧めしますまたは楕円曲線因数分解。Pollard の rho アルゴリズムは実装がより簡単で、その大きさの数に対して同等の時間で要因を見つけることができるため、これが私の最初の推奨事項です。

于 2012-10-05T19:56:21.903 に答える
0

Int は小さすぎて、パフォーマンスの問題が発生する可能性があります。ブーストを使用してアルゴリズムの時間を測定しようとしましたが、有用な出力が得られませんでした (速すぎます)。したがって、整数についてまったく心配する必要はありません。

i*i を使用すると、15.097 秒で 1.000.000 個の 9 桁の整数を計算できました。アルゴリズムを最適化するのは良いことですが、(状況によって異なりますが) 時間を「無駄にする」のではなく、小さな改善が本当に努力する価値があるかどうかを検討することが重要です。ラリーで 10 秒で 1.000.000 整数を計算できるようにする必要があるのか​​、それとも 15 秒で十分なのかを自問する必要がある場合があります。

于 2012-10-05T18:45:11.573 に答える