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

79愛的鼓勵 1訂閱站台

作法 : DP

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

所以我提供一個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 input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
short int pp[1000001]={0}; 
int KILL[1000001]={0};
void prime()  
{  
 int a,b,m=0;
 for(a=3;a<=1000;a=a+2)     
      if(pp[a]==0)     
        {     
           for(b=3;a*b<=1000000;b=b+2)
             pp[a*b]=a;
        }  
}  
int Divisors (int num,int s)
{
   if(pp[num]==0&&num%2!=0) return 2;
   if(num%2==0) s=2;
   int a,time=0;
   while(num%s==0)
         {
         time++;
         num/=s;
         }
    return KILL[num]*(time+1);
}
main()  
{  
 prime(); 
 KILL[1]=1;
 int n,a; 
 for(a=2;a<=1000000;a++)
    KILL[a]=Divisors (a,pp[a]);
 while(n=input())
     printf("%d\n",KILL[n]);
 return 0;
}