摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 生成因數

最基本的暴力解法在最下面

說明一個"比較"快的解法,
首先先將N分解成質因數的模式

假使是2^5*3^2*5^3

利用樹枝狀

1        1       1
2        3       5
4        9      25
8              125
16
32

自己做連線...之後生出所有因數

之後再做排序!

/*********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int Prime[5200]={0},p; 
char pp[50001]={0};
int N,M,S;
int prime()  
{  
 int a,b,m=1;
 Prime[0]=2;  
 for(a=3;a<=50000;a=a+2)     
      if(pp[a]==0)     
        {     
           Prime[m]=a;     
           m++;     
           for(b=3;a*b<=50000;b=b+2)     
             pp[a*b]=1;     
        }  
   return m;  
}
int value[51][51]={0},time[51]={0},top=0;
int Divisors (int num)
{
   int a,b,C=1;
   for(a=0;a<p&&Prime[a]*Prime[a]<=num&&num!=1;a++)
      {
        if(num%Prime[a]==0)
          {
             ++top;
             value[top][0]=1;
             while(num%Prime[a]==0)
                  {
                   num/=Prime[a];
                   ++time[top];
                   value[top][time[top]]=value[top][time[top]-1]*Prime[a];
                  }
          }
      }
    if(num!=1)
      {
      ++top;
      ++time[top];
      value[top][0]=1;
      value[top][1]=num;
      }
}
int sum,t;
int ans[1000];
void make (int now,int s,int end)
{
   int a;
  
   if(now>=end+1)
       {
        ans[t++]=s;
        return;
       }
   for(a=0;a<=time[now];a++)
      make(now+1,s*value[now][a],end);
}
int partition(int[], int, int);   
void quicksort(int[], int, int);
main()
{
 p=prime();
 int a,b;
 while(scanf("%d",&N)==1)
    {
     top=0;
     for(a=0;a<51;a++) time[a]=0;
     Divisors(N);
     sum=0;t=0;
     make(1,1,top);
     quicksort(ans,0,t-1);
     for(a=0;a<t;a++)
        printf("%d ",ans[a]);
        printf("\n");
    }
 return 0;  
}
int partition(int num[],int left,int right)   
{  
  int a=left-1,b,s=num[right];  
  for(b=left;b<right;b++)  
   {  
     if(num[b]<=s)  
       {  
         a++;  
         int temp;  
         temp=num[a];  
         num[a]=num[b];  
         num[b]=temp;   
       }   
   }   
         int temp;  
         temp=num[a+1];  
         num[a+1]=num[right];  
         num[right]=temp;   
   return a+1;   
}   
void quicksort(int num[],int left,int right)  
{  
 int q;  
 if(left<right)   
   {  
     q=partition(num,left,right);  
     quicksort(num,left,q-1);  
     quicksort(num,q+1,right);   
   }   
}  

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
 int n;
 while(scanf("%d",&n)==1)
      {
        int a;
        int ans[1000],top=0,flag=1;
        if(n%2==1) flag++;
        int sq=sqrt(n);
        for(a=1;a<=sq;a+=flag)
           if(n%a==0)
            {
              printf("%d ",a);
              if(n/a!=a)
                 ans[top++]=n/a;
            }
        for(a=top-1;a>=0;a--)
           printf("%d ",ans[a]);
           printf("\n");
      }
 return 0;
}