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

有一个简单的更改会在一定程度上缩短运行时间：将所有 2 分解，然后只检查奇数。

于 2012-10-05T18:48:01.033 回答
3

如果你使用

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

它可能比 i <= sqrt(n) 运行得快得多

顺便说一句，您应该尝试处理负 n 的因素，或者至少确保您永远不会传递一个负数

于 2012-10-05T18:42:45.713 回答
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)

如果unsigned int是典型的 32 位类型，则数字太小，任何更高级的算法都无法获得回报。试炼师平时的强化当然是值得的。

如果您将除以 2 移出循环，并且只除以循环中的奇数，如Pete Becker 所述，您实际上是将输入数字分解所需的除法数减半，从而加快该函数几乎是 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 位，那么使用更高级的算法之一将是有利可图的。您仍然应该从试验除法开始，以找到小的主要因素（无论小应该意味着<= 1000,还是可能需要测试，我的直觉是平均而言，较小的值之一会更好）<= 10000。如果在试除法阶段之后因式分解尚未完成，则使用例如 Miller-Rabin 测试的确定性（针对所讨论的范围）变体检查剩余因子是否为素数。如果不是，请使用您最喜欢的高级算法搜索一个因子。对于 64 位数字，我推荐Pollard 的 rho 算法<= 100000<= 1000000或椭圆曲线分解。Pollard 的 rho 算法更容易实现，并且对于这么大的数字可以在可比较的时间内找到因子，所以这是我的第一个建议。

于 2012-10-05T19:56:21.903 回答
0

Int 是遇到任何性能问题的方式。我只是试图用 boost 来测量你的算法的时间，但没有得到任何有用的输出（太快）。所以你根本不应该担心整数。

如果你使用 i*i 我能够在 15.097 秒内计算出 1.000.000 个 9 位整数。优化算法是件好事，但与其“浪费”时间（取决于您的情况），重要的是要考虑一个小的改进是否真的值得付出努力。有时您必须问自己是否需要能够在 10 秒内计算 1.000.000 个整数，或者 15 是否也可以。

于 2012-10-05T18:45:11.573 回答