优化我的代码以查找给定整数的因子

Question

这是我的代码,但我想优化它.我不喜欢它在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;
}

Answer 1

以下是关于如何在"正确的"c ++中执行此操作的建议(因为您标记为c ++).

PS.差点忘了提一下:我优化了去掉的电话sqrt:)

在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;