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

79愛的鼓勵 1訂閱站台

作法 : 建表

這個數列似乎陡降的很快

10萬以內 L<=7

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

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>  
int Prime[5200]={0},p; 
char pp[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]=1;     
        }  
   return m;  
}  
int Divisors (int num)
{
   if(pp[num]==0) return 2;
   int a,b,C=1;
   for(a=0;a<p&&Prime[a]<=sqrt(num)&&num!=1;a++)
      {
        int time=0;
        if(num%Prime[a]==0)
          {
             while(num%Prime[a]==0)
                {
                   num/=Prime[a];
                   time++;
                }
             C*=(time+1);
          }
      }
    if(num!=1)
      C*=2;
    return C;
}
main()  
{  
 p=prime(); 
 int KILL[100001]={0};
 int n,a; 
 for(a=2;a<=100000;a++)
    KILL[a]=Divisors (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;     
}