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

79愛的鼓勵 1訂閱站台

作法 : 動態規劃(DP)

分解這些數字當然很簡單,但是要做得好、快又是另一回事

在這裡提供4種程式碼.

第1程式碼 : 最原始的分解
第2程式碼 : 利用之前所紀錄過的,直接算 (記憶體+大)
第3程式碼 : 是先判斷質數(線性篩法)+第2程式碼 (記憶體+大)
第4程式碼 : 先利用線性篩法得知每個數必有的質因數,然後利用DP 不斷的從之前已知的 東西得知+快其速度

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int math[5000],p,n;
char num[2000]={0};
int sum[1000001]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=1000000;a++)
     {
       sum[a]=sum[a-1];
       int sqr=(int)sqrt(a),temp=a;
        for(b=0;b<p&&math[b]<=sqr;b++)
           while(temp%math[b]==0)
              {
                 temp=temp/math[b];
                 sum[a]++;
              }
        if(temp!=1)  sum[a]++;
     }
}
int prime()  
{  
 int a,b,m=1;
 math[0]=2;
 for(a=3;a<1000;a=a+2)     
      if(num[a]==0)     
        {     
           math[m]=a;     
           m++;     
           for(b=3;a*b<=1000;b=b+2)     
             num[a*b]=1;     
        }  
   return m;  
}
main()
{
 p=prime();
 Divisors ();
 while(scanf("%d",&n)==1)
     printf("%d\n",sum[n]);
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int math[5000],p,n;
char num[2000]={0};
int sum[1000001]={0},ar[1000001]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=1000000;a++)
     {
       sum[a]=sum[a-1];
       int temp=a;
        for(b=0;b<p&&math[b]*math[b]<=a&&temp!=1;b++)
           while(temp%math[b]==0)
              {
                 temp=temp/math[b];
                 ar[a]++;
                 if(temp<a)
                  {
                    ar[a]+=ar[temp];
                    temp=1;
                  }
              }
        if(temp!=1)  ar[a]++;
        sum[a]+=ar[a];
     }
}
int prime()  
{  
 int a,b,m=1;
 math[0]=2;
 for(a=3;a<1000;a=a+2)     
      if(num[a]==0)     
        {     
           math[m]=a;     
           m++;     
           for(b=3;a*b<=1000;b=b+2)     
             num[a*b]=1;     
        }  
   return m;  
}
main()
{
 p=prime();
 Divisors ();
 while(scanf("%d",&n)==1)
     printf("%d\n",sum[n]);
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int math[5000],p,n;
char num[1000001]={0};
int sum[1000001]={0},ar[1000001]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=1000000;a++)
     {
       sum[a]=sum[a-1];
       if(a%2==0||num[a]==1)
       {
         int temp=a;
         for(b=0;b<p&&math[b]*math[b]<=a&&temp!=1;b++)
            while(temp%math[b]==0)
               {
                  temp=temp/math[b];
                  ar[a]++;
                  if(temp<a)
                   {
                     ar[a]+=ar[temp];
                     temp=1;
                   }
               }
         if(temp!=1)  ar[a]++;
        }
       else ar[a]=1;
        sum[a]+=ar[a];
     }
}
int prime()
{  
 int a,b,m=1;
 math[0]=2;
 for(a=3;a<1000;a=a+2)     
      if(num[a]==0)     
        {     
           math[m]=a;     
           m++;     
           for(b=3;a*b<=1000000;b=b+2)     
             num[a*b]=1;     
        }  
   return m;  
}
main()
{
 p=prime();
 Divisors ();
 while(scanf("%d",&n)==1)
     printf("%d\n",sum[n]);
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int n;
short int num[1000001]={0};
int sum[1000001]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=1000000;a++)
     {
       sum[a]=sum[a-1];
       if(a%2==0||num[a]!=0)
        {
            if(a%2==0)
                 sum[a]+=(sum[a/2]-sum[a/2-1])+1;
            else
                 sum[a]+=(sum[a/num[a]]-sum[a/num[a]-1])+1;
        }
       else sum[a]++;
     }
}
void prime()
{  
 int a,b;
 for(a=3;a<1000;a=a+2)     
      if(num[a]==0)     
        {     
           for(b=3;a*b<=1000000;b=b+2)     
             num[a*b]=a;      /*Here*/
        }  
}
main()
{
 prime();
 Divisors ();
 while(scanf("%d",&n)==1)
     printf("%d\n",sum[n]);
 return 0;
}