求解大数分解的有效率的算法？？

funnyt

各位DX
如题，
最指点一下。

liubinbj

怎么个分解法阿？

funnyt

所有的数都是由素数组成的
分解就是说分为素数的乘积
eg：24=2*2*2*3
(此专指正整数)

funnyt

看过这里的好多精华文章
对N多版主相当佩服！！

liubinbj

要最快的？还是简单点的？

funnyt

都要可以吗？
学习一下.

liubinbj

明天抽空写一个，今天台湾了。

funnyt

好的
谢谢

funnyt

写了一个
可惜不能处理（1<<56）以上的
不知到DX们有什么解决方法没有
#include "stdio.h"
#include "math.h"
f(__int64 n)
{
        __int64 i, j=sqrt(n);
        for(i=2;i<=sqrt(n)+1;i++)
        {
                if(n%i==0)
                        printf("%d  ",i),
                        n/=i,
                        j=sqrt(n),
                        i=(i>j?2i-1));
        }
        if(n==1)return 0;
        if(i==j+2)printf("%d  ",n);
        return 0;
}
main()
{
        f(24203);
}

liubinbj

1. 
   
2. int table[14094]={
   
3. 2,3,5,7,11,13,17,19,23,
   
4. 25,29,31,35,37,41,43,47,49,53,
   
5. 59,61,67,71,73,77,79,83,89,91,
   
6. 
   
7. 太多了贴不上
   
8. 
   
9. 65369,65371,65377,65381,65383,65389,65393,65399,65407,65411,
   
10. 65413,65419,65423,65431,65437,65441,65447,65449,65453,65459,
    
11. 65467,65473,65477,65479,65489,65491,65497,65501,65503,65507,
    
12. 65509,65519,65521,65531,65533,};
    
13. 
    
14. 
    
15. int defact(int n,int factor[],int num)
    
16. {
    
17. 
    
18.         int co=0;
    
19.         int mark;
    
20.         while(n>1) {
    
21. 
    
22.                 mark=0;
    
23.                 for(int i=0;i<14094;i++) {
    
24.                         if(n%table[i]==0) {
    
25.                                 n/=table[i];
    
26.                                 mark=1;
    
27.                                 if(co >= num) return -1;
    
28.                                 factor[co++]=table[i];
    
29.                                 break;
    
30.                         }
    
31.                 }
    
32. 
    
33.                 if(!mark) {
    
34.                         if(co >= num) return -1;
    
35.                         factor[co++]=n;
    
36.                         break; //这轮没找到因子
    
37.                 }
    
38.         };
    
39. 
    
40.         return co;
    
41. }
    
42. 
    

复制代码

这个我觉得最快了，上面是计算到65536的质数表，计算时只需要除每个质数就可以了，除的尽就是银子。这个算法适合计算量大的场合。少量计算就不要搞那么大的表了吧。