用程序实现分解质因数

求算法 时间复杂度要低一点

你所说的数是多大以内的，假设是m，那么你先用筛选法选出 m以下的素数,然后用最小的开始除原来的数并输出每次的除数，每当不能整除时，素数的计数器加1，当数组内元素大于被除数时，则结束循环，被除数为最后一个因子

int s[100]  //假设这个是存放m以下素数的数组

for(i=0; ;i++)
{
 if(s[i]>m)
 {
  cout<<m<<endl;
  break;
 }
 while(m%s[i]==0)
 {
  m%=s[i];
  cout<<s[i]<<" ";
 }
}大致是这样,输出格式之类的根据需求自己控制下吧，在分解前用筛选法先准备好素数对提高效率是很多的

#include<stdio.h> 　　#include<math.h> 　　int main() { 　　int i,b; 　　long long in; 　　freopen("F://1.txt","r",stdin); 　　freopen("F://2.txt","w",stdout); 　　while(scanf("%lld",&in)!=EOF) { 　　b=0; 　　for(i=2;in!=1;i++) 　　if(in%i==0) { 　　in/=i; 　　b?printf(" %d",i):printf("%d",i),b=1; 　　i--; 　　} 　　printf("\n"); 　　} 　　return 0; 　　}

#include   <stdio.h> #include   <stdlib.h> #include   <math.h> void   pr(long   p,   int   i); int   main() {     int     i;     long   x,   x2,   p;     char   s[512];     for   (;;)   {         printf( "\n>   ");         gets(s);         x   =   atol(s);         pr(x,   0);         if   (x   <   2)   break;         p   =   2;         for   (i   =   0;   (x   %   p)   ==   0;   i++)             x   /=   p;         if   (i   >   0)   pr(p,   i);         if   (x   ==   1)   continue;         x2   =   (long)sqrt((double)x);         for   (p   =   3;   p   <=   x2;   p   +=   2)   {             for   (i   =   0;   (x   %   p)   ==   0;   i++)                 x   /=   p;             if   (i   >   0)   pr(p,   i);             x2   =   (long)sqrt((double)x);         }         if   (x   >   1)   pr(x,   1);     }     return   0; } void   pr(long   p,   int   i) {     static   char   c   =   '= ';     if   (i   ==   0)   {         printf( "#   %ld ",   p);         c   =   '= ';     }     else   {         printf( "   %c   %ld ",   c,   p);         if   (i   >   1)   printf( "^%d ",   i);         c   =   '* ';     } } 运行结果如下: >   123456 #   123456   =   2^6   *   3   *   643 >   1234567890 #   1234567890   =   2   *   3^2   *   5   *   3607   *   3803