2

有人可以帮助纠正我的算法吗？我已经在几个数字上对其进行了测试，但它没有输出完整的因式分解。对于具有大量因子的数字，它完全失败了。

int num = 20;

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

编辑：提供的两个答案不起作用，仍然没有得到完整的结果。

EDIT2：除数与因子

4

4 回答 4

12

从您对 @ 的评论来看Luchian Grigore，您将除数与(prime) factorization混淆了。一个数的除数是所有num % i == 0为真的数。因式分解意味着num通过较小数字的乘积来表示。如果你想要分解的唯一性，你通常使用素数分解。

要获得所有除数，您的代码应该是

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 之后，您退出循环，因为i它递增到 3 并num变为 2。

以下应该有效：

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 回答