最大約數問題（詳細代碼）

#include<iostream>

using namespace std;

int Simple_count(int a,int b);//累除法

int numlist(int a[])//建立素數表

{

 int flag=0;//确定數組目前存儲素數的位置

 bool repeat=true;//循環标志位設定

 int j=0;

 for(int i=2;i<10000;i++)//将通過設定i的上限來擴大搜尋的範圍

 {

  while(repeat)

  {

   if((j==flag)&&(i%a[flag]!=0))//判斷是否已經到了目前素數表的最後一個元素，還不能整除的，把目前數字推入素數表

   {

    repeat=false;

    flag++;

    a[flag]=i;

   }

   else

    if(i%a[j]==0)//如果能整除跳出while語句

    {

     repeat=false;

    }

    else//否則繼續判斷

     j++;

  }

  repeat=true;//i每進行一次測試前，必須置值為真

  j=0;//下一個數的除數應該從a[0]開始，是以j應該置零

 }

 return flag;//傳回計算的個數

   //其實有可能出現誤差，如果這個含有最大約數的數還有一個很大的素數因子沒有檢測出來

   //又或者有一個數由于其素數公因子太多，是以少計算進去，可能存在誤差

   //但是從另一方面考慮，如果這個數真的含有最多的約數，那麼它的素數公因子必須很小

   //是以，出錯的機率必須和a和b之間存在的個數有關

}

int test(int a[],int start,int finish,int flag)

    bool repeat=true;

 int testnumber=start;//存儲含有最大約數的數，以備檢查（利用累除法檢查）

 int numberflag=0;//設定比較位

 int statist=1;//到底應該設定統計值為多少需要分析 

 int b[10000]={0};//初始化目前标志位記載有多少個這樣相同的素數，并且初始化

 int j=0;//儲存指向标志位數組的目前光标

 int temp=0;//循環除法的載體

 for(int i=start;i<=finish;i++)

  //j不能否超越flag的存在

  for( j=0;i>=a[j];j++)//不能超過素數表的界限，但是必須排除這個數小于10000，當這個數很小時，沒有必要比較下去 

  {

   if(j>flag)

   {

    break;

   }

   else

       temp=i;

               while(temp%a[j]==0)//如果能夠整除，标志位加1，同時記得除去已經添加的次數

      {

                   b[j]++;

              //記住a和b的下标是對應的

                 temp=temp/a[j];

      }

  }

  //現在統計這個數含有的公因子個數

  for(int k=0;k<=j;k++)

   if(b[k]!=0)

    statist=statist*(b[k]+1);

   //cout<<i<<"的約數個數:"<<statist<<endl;

  if(numberflag<statist)//取其中最大的數字

   numberflag=statist;

   testnumber=i;

  statist=1;//重置

  for( k=0;k<=j;k++)

    b[k]=0;  

 cout<<"獲得的測試值是"<<testnumber<<endl;

 int middlenumber=Simple_count(start,finish);

 cout<<middlenumber<<endl;

 if(numberflag!=middlenumber)

  cout<<"計算出現誤差"<<endl;

 return numberflag;

int Simple_count(int a,int b)//當a和b之間的個數在50左右時，可以直接使用類除法（通過計算測試時間表明

{//當a的值大于100000000時，每計算一個數，需要花費接近1s的時間，意昧着：計算10萬個數需要半小時

 int number=0;//統計約數的個數

 int flag=0;//設定比較數，當後一個數的約數個數大于前一個數時，重置

 for(int i=a;i<=b;i++)//外層循環從a到b

  for(int j=1;j<=i/2;j=j+1)//内層循環檢測從2到自身

   if(i%j==0)

    number++;

  number++;//自身也是一個約數，需添加進去

  if(number>flag)//重置标志位

   flag=number;

  number=0;//剛才忘記恢複計數值為0

 return flag;

int main()

  int a[10000]={2,0};//素數表初始化

  int flagnumber=0;

  flagnumber=numlist(a);//獲得目前的素數表，還有目前素數表的個數flag+1，表示目前素數表從0開始

  cout<<flagnumber<<endl;

  cout<<a[1000]<<endl;

    int min;

    int max;//擷取目前的範圍

    int result;//擷取目前的結果

  cout<<"請輸入兩個數，以便擷取目前的範圍";

  cout<<endl;

  cin>>min>>max;

  if(max-min<50)

   result=Simple_count(min,max);

  else

   result=test(a,min,max,flagnumber);

  cout<<result<<endl;

  return 0;

     本文轉自fengyuzaitu 51CTO部落格，原文連結：http://blog.51cto.com/fengyuzaitu/1580844，如需轉載請自行聯系原作者