2

誰かが私のアルゴリズムを修正するのを手伝ってもらえますか？いくつかの数値でテストしましたが、完全な因数分解は出力されません。多数の要因を持つ数値の場合、完全に失敗します。

int num = 20;

for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
    }
}

編集：提供された2つの答えは機能しませんでしたが、それでも完全な結果は得られませんでした。

EDIT2：除数VSファクター

4

4 に答える 4

12

@へのコメントから判断すると、除数と（素因数）因数分解Luchian Grigoreを混同しています。ある数の約数は、すべて真である数です。因数分解とは、より小さな数の積での表現を取得することを意味します。因数分解の一意性が必要な場合は、通常、素因数分解を使用します。num % i == 0num

すべての除数を取得するには、コードは次のようになります。

for ( int i = 1; i <= num; ++i ) // note that 1 and num are both trivially divisors of num
{
    if ( num % i == 0 ) // only check for divisibility
    {
        std::cout << i << std::endl;
    }
}

（素因数分解）を取得するには、

for ( int i = 2; i <= num; ++i )
{
    while ( num % i == 0 ) // check for divisibility
    {
        num /= i;
        std::cout << i << std::endl;
    }
    // at this point, i cannot be a divisor of the (possibly modified) num.
}
于 2012-08-16T20:53:18.070 に答える
2

問題はi、除数であっても増加していることです。すべての発生を見つけない限り、増加してはいけません。

したがって、4の場合、2は2回あります。しかし、最初に遭遇した2の後、i3にインクリメントされてnum2になったため、ループを終了します。

以下が機能するはずです。

for(int i = 2; i <= num; )
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
    }
    else
    {
        i++;
    }
}
于 2012-08-16T20:39:06.557 に答える
1 
for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
        num = num/i;    
        i--; // Add this to account for multiple divisors
    }
}

for(int i = 2; i <= num; i++)
{
    if(num%i == 0)
    {
        cout << i << endl;
        cout << num << endl;
    }
}
于 2012-08-16T20:41:43.140 に答える
0

これは機能するはずです。移動コンストラクターにはc++11を使用する必要があることに注意してください。そうしないと、代わりにstd :: list＆を渡すことになります。

std::list<int64_t> factor(int64_t f)
{
    std::list<int64_t> factors;
    for(int64_t ii = 2; ii<=f; ii++) {
        while(f % ii == 0) {
            f = f/ii;
            factors.push_back(ii);
        }
    }

    return factors;
}
于 2014-08-01T19:09:31.147 に答える