C语言 计算整数的所有因子的最快算法是什么？

What is the fastest algorithm to calculate all factors of an integer number?

提问by Biswajit

I have written this block of code but it is consuming lots of time to calculate... Can you help me finding out an efficient way to do it?

我已经编写了这段代码，但是计算要花费很多时间......你能帮我找出一种有效的方法吗？

int tag;
int* factors(int n)
{
    int a[1000000];
    for(int i=1;i<=n/2;i++)
        if(n%i==0)
            a[++tag]=i;
    a[++tag]=n;
    return(a);
}

This brute force method is very hefty in terms of complexity... Is there any better feasible solution to this problem?

这种蛮力方法在复杂性方面非常庞大......有没有更好的可行解决方案来解决这个问题？

回答by mikyra

Until now no one has come up with a muchfaster algorithm. This doesn't necessarily have to mean there isn't any as on the other hand it also hasn't been proven that it is impossible to do it much faster.

到现在为止还没有人想出了一个多更快的算法。这并不一定意味着没有，因为另一方面，也没有证明不可能更快地做到这一点。

One optimization you might want to take into account is that it's not necessary to search up to n/2 you can already stop when sqrt (n) is reached.

您可能想要考虑的一种优化是，没有必要搜索最多 n/2，您可以在达到 sqrt (n) 时停止。

... and be sure to to choose a different storage location for your numbers if you really want to return a list of all candidates found as already mentioned in "chris" comment.

...如果您真的想返回在“克里斯”评论中已经提到的所有候选人的列表，请务必为您的号码选择不同的存储位置。

EDIT:

编辑：

As I was adverted that there is a rather large variety of algorithms available that in terms of time complexity might run a little bit faster than the one you asked about it might be indicated to add a few more words than the short comment given above.

正如我被告知有相当多的算法可用，就时间复杂度而言，它们的运行速度可能比您询问的算法快一点，可能会指示添加比上面给出的简短评论更多的单词。

While besides the most obvious possibility to safe some computation time by just running the loop in steps of 2 after first dividing it down to an odd number there are still some other tricks available I didn't mention them as substantiallyfaster in the answer given above.

而除了通过后，首先将它归结为奇数只是运行在2个步骤的循环最明显的可能性安全一些计算时间还存在一些其他的技巧可我并没有作为提及他们基本上在上面给出的答案更快.

The main reason that led to this decision is, that while for example cutting to number of iterations down by a factor of 2 seems like a big win to make in comparison to the expected growth in runtime with growing numbers a gain measured in terms of a constant becomes so small that in complexity theory there even won't be made any difference at all and both algorithms will be said to have (almost) the same time complexity.

导致这个决定的主要原因是，例如，将迭代次数减少 2 倍，与运行时的预期增长相比似乎是一个巨大的胜利，随着数字的增长，增加了一个衡量的收益常数变得如此之小，以至于在复杂性理论中甚至根本不会产生任何区别，并且可以说两种算法具有（几乎）相同的时间复杂度。

Even if it was possible to get a constantgain of hundreds of a billion times the runtime of the original algorithm there still wouldn't be made any difference between both of them at all.

即使有可能获得原始算法运行时间数千亿倍的恒定增益，它们之间仍然没有任何区别。

The bigger the numbers get the less influence any constant be it as big as you may ever be able to image plays in terms of runtime if it is also rapidly growing with the magnitude of the number you are adressing.

数字越大，任何常数的影响就越小，如果它也随着您要处理的数字的大小而迅速增长，那么就运行时间而言，它可能与您所能想象的一样大。

One very special barrier in terms of time complexity often regarded as the border between practically feasible and merely impossible is that of so called polynomialruntime.

在时间复杂度方面的一个非常特殊的障碍通常被认为是实际可行和完全不可能之间的边界，就是所谓的polynomial运行时间。

This means nothing else than that even though the runtime might grow drastically with growing nit is still possible to describe this growth with a constantexponent k, such that the runtime is something around n^k.

这意味着即使运行时可能会随着增长而急剧增长，n但仍然可以用一个常数指数来描述这种增长k，这样运行时就差不多了n^k。

On the other hand an algorithm without polynomialruntime can't be measured with any exponent how ever big you may want to make it.

另一方面，没有polynomial运行时的算法不能用任何指数来衡量，你可能想要它有多大。

To give an example why this difference might really matter at all let's take a look at two imaginary algorithms. The first one having polynomial runtime, say n^10and just another one say this one with runtime n!.

为了举例说明为什么这种差异可能真的很重要，让我们看一下两个虚构的算法。例如，第一个具有多项式运行时，n^10而另一个则用 runtime 说这个n!。

While it doesn't seem to bad for small numbers, let's say n is just 10 here algorithm one takes 10^10 = 10000000000time units while with only 3628800units our second algorithm seems to run even a lot faster.

虽然它对于小数似乎并不坏，但假设 n 只是 10，这里算法第一个需要10^10 = 10000000000时间单位，而只有3628800单位我们的第二个算法似乎运行得更快。

The problem with our algorithm two is, that compared to algorithm one its runtime will grow dramatically faster. At n=100you get something like: 100000000000000000000for algorithm one while it is already something like 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000for algorithm two.

我们的算法二的问题是，与算法一相比，它的运行时间会增长得更快。在n=100你喜欢的东西：100000000000000000000对算法之一，而这已经是类似93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000的算法两项。

Pushing frontiers even further with n=1000we end up with: algorithm one at 1000000000000000000000000000000while our second algorithm will take something like 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

进一步推动边界，n=1000我们最终得到：算法一，1000000000000000000000000000000而我们的第二个算法将采用类似402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.

If you don't believe just calculate it yourself. The bcmanual even contains an example of how to implement the factorial function.

不信你自己算算。该bc手册甚至包含如何实现阶乘函数的示例。

But don't get dizzy while counting digits... It might be interesting to know how many trailing zeroes we would have have to add to 10 to get the factor by which to multiply the age of our universe to get such a big span of time even if we measured in units of planck time. Unfortunately I don't know.

但是在计算数字时不要头晕……知道我们必须在 10 上加上多少个尾随零才能得到乘以我们的宇宙年龄以获得如此大的跨度的因子，这可能会很有趣。即使我们以普朗克时间为单位测量时间。不幸的是我不知道。

What's interesting about all that is the fact that until today there isn't any known algorithm that can perform factorization in polynomialtime.

有趣的是，直到今天，还没有任何已知的算法可以及时执行因式分解polynomial。

As it is not only an interesting field of research int itself the practicalimpossibility to factorize large integer numbers also plays an important role in the RSA public key encryption algorithm which is in widespread use today, so almost naturally there has already been a lot of resarch in this area.

由于它不仅是一个有趣的研究领域本身，分解大整数的实际不可能在当今广泛使用的 RSA 公钥加密算法中也起着重要作用，因此几乎很自然地已经有很多研究在这个领域。

Discovering algorithms that (without breaking the barrier already mentioned) run sligthlyfaster than the algorithm you supposed.

发现算法（不打破已经提到的障碍）运行速度比您想象的算法稍快。

As "Jim Balter" alredy correctly annotated in his comment you might want to take a look at the referenced article (see: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose) to take a look upon the methods others already came up with.

由于“Jim Balter”已经在他的评论中正确注释，您可能需要查看参考文章（请参阅：http: //en.wikipedia.org/wiki/Integer_factorization#General-purpose）以了解这些方法别人已经想出来了。

This article also mentioned by "Jim" might be another interesting resource: (see: What is the fastest factorization algorithm?)

“Jim”也提到的这篇文章可能是另一个有趣的资源：（请参阅：什么是最快的分解算法？）

Another interesting link to take a look upon might be the list of the RSA factoring challange winners of the past years to somehow get an idea where the border between feasible and almost impossible may lies today. (http://en.wikipedia.org/wiki/RSA_Factoring_Challenge)

另一个值得查看的有趣链接可能是过去几年 RSA 因式分解挑战获胜者的名单，以某种方式了解今天可行和几乎不可能之间的界限在哪里。( http://en.wikipedia.org/wiki/RSA_Factoring_Challenge)