是否有任何最快的算法来查找给定数字的因子？ [英] is there any fastest algorithm to find factors of given number?

问题描述

有没有最快的算法来查找给定数字的因子？

在10 ^ 9 ...

小于O（n）的范围内>
for（i = 2; i< = n / 2; i ++）

{

if（n％i == 0）

printf（i）;

}

解决方案

从这里开始： http://en.wikipedia.org/wiki/Integer_factorization [ ^ ]

例如，您可以迭代一系列预先计算过的素数。

< blockquote>如何知道最快是什么意思？

（a）在生产模式下执行最快

（b）最快准备数据（例如计算查找表）

（c）发展最快



假设您的目标是（a）并且您可以花费任何时间来开发它（即（b）和（c））并假设你有足够的具有足够访问速度的cient存储空间，我会在开发期间使用
1）为所有10 ^ 9个数字生成查找表;-)

1.1）计算全部给定数字的主要因素

1.2）产生所有因素的所有组合以产生所有因素

2）在制作中，使用该查找表



例如对于 n = 63

1）素数因素： 3 x 3 x 7

2）组合：

（3）x（3）x（7）= 3 x 3 x 7 
（3 x 3）x（7）= 9 x 7 
（3）x（3 x 7）= 3 x 21 
 

现在你可以想到空间优化，但这总是会降低执行速度。例如。将1.2移动到生产模式，或压缩表格（将表格安排为树或分区并压缩并仅缩放所需的部分等），...



干杯

Andi

is there any fastest algorithm to find factors of given number?
in the range of 10^9...
less than O(n)
for(i=2;i<=n/2;i++)
{
if(n%i==0)
printf(i);
}

解决方案

Start here : http://en.wikipedia.org/wiki/Integer_factorization[^]

You could, for instance, iterate over a sequence of pre-computed prime numbers.

How to know what "fastest" mean?
(a) fastest to execute in production mode
(b) fastest to prepare data (e.g. calculate a lookup table)
(c) fastest to develop

Assuming you aim for (a) and that you can spend any amount of time to develop it (i.e. (b) and (c)) and assuming you have sufficient storage space with adequate access speed, I would go for
1) during development, produce a lookup table for all 10^9 numbers ;-)
1.1) calculate all prime factors for a given number
1.2) produce all combinations of the prime factors to produce all factors
2) in the production, use that lookup table

E.g. for n = 63
1) prime factors: 3 x 3 x 7
2) combinations:

(3) x (3) x (7) = 3 x 3 x 7
(3  x  3) x (7) = 9 x 7
(3) x (3  x  7) = 3 x 21

Now you can think of space optimizations, but this will always go on the cost of execution speed. E.g. move 1.2 to production mode, or compress the table (arrange the table as a tree or partition and compress and only deflate the needed part, etc.), ...

Cheers
Andi

这篇关于是否有任何最快的算法来查找给定数字的因子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！