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

79愛的鼓勵 1訂閱站台

作法 : 因數分解

由於大家基本上都會因數分解...在此就不提供了

所以我提供一個DP的分解方式

首先先建出每個數必有的"質因數"

EX處理 :

2~23 都分解好了 並知道個數存在陣列中

24=2^3*3

之後 我從我紀錄中知道24 必有3 這個質因數

因此我將 24 / 3 看能整除幾次(TIME)

剩下 24 就會變成 8
因此我知道 8 的個數 所以 24的因數個數 = 8的因數個數*(TIME+1)

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

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>  
int Prime[5200]={0},p; 
int pp[100001]={0}; 
int KILL[100001]={0};
int prime()  
{  
 int a,b,m=0;  
 for(a=2;a<=317;a++)     
      if(pp[a]==0)     
        {     
           Prime[m]=a;     
           m++;     
           for(b=2;a*b<=100000;b++)     
             pp[a*b]=a;     
        }  
   return m;  
}  
int Divisors (int num,int s)
{
   if(pp[num]==0) return 2;
   int a,time=0;
   while(num%s==0)
         {
         time++;
         num/=s;
         }
    return KILL[num]*(time+1);
}
main()  
{  
 p=prime(); 
 KILL[1]=1;
 int n,a; 
 for(a=2;a<=100000;a++)
    KILL[a]=Divisors (a,pp[a]);
 /* freopen("input.txt", "rt", stdin);
  freopen("output.txt", "w+t", stdout);*/
  while(scanf("%d",&n)==1)
    {
       int L=1;
       printf("%d",n);
       while(n!=2)
          {
             n=KILL[n];
             printf("->%d",n);
             L++;
          }
          printf("\nL=%d\n",L);
    }
 return 0;     
}