求最大公约数的几种方法

   1:  #include "stdafx.h"

   2:  #include <iostream>

   3:  using namespace  std;

   4:  #include<time.h>  

   5:  #include<math.h>

   6:  const int Max = 10;

   7:  //采用连续整数检测   ，   利用求最大公约数的性质解题，有点意思。

   8:  void gcd1(int a, int b)

   9:  {

  10:      int t;

  11:      int count = 0;

  12:      t = b;

  13:      while(1)

  14:      

  15:      {

  16:          count++;

  17:          if (a%t == 0)

  18:        {

  19:            if (b%t==0)

  20:            {

  21:                break;

  22:            }

  23:            else

  24:            {

  25:              t = t - 1;

  26:            }

  27:         }

  28:         else

  29:         {

  30:              t = t - 1;

  31:         }

  32:      }

  33:      cout << "采用连续整数检测算法输出的结果是："<< endl;

  34:      cout << "输出最大公约数是："<< t << endl;

  35:      cout << "最大迭代次数是："<< count << endl;

  36:      

  37:  }

  38:   

  39:  //采用欧几里得算法   ，   又叫辗转相除算法

  40:  void gcd2(int a, int b)

  41:  {

  42:     int r = a % b;

  43:     int count = 0;

  44:     while(r != 0)

  45:     {

  46:         count++;

  47:         a = b;

  48:         b = r;

  49:         r = a % b;

  50:     }

  51:     cout << "采用欧几里得算法输出的结果是："<< endl;

  52:     cout << "输出最大公约数是："<< b << endl;

  53:     cout << "最大迭代次数是："<< count << endl;

  54:  }

  55:   

  56:  //采用分解质因数法

  57:  void gcd3(int a, int b)

  58:  {

  59:     int x[Max]={0},y[Max]={0},z[Max]={0};

  60:     int count1 = 0, count2 = 0, count3 = 0, count = 0;

  61:     // 将a分解质因数，并将质因数放入x数组中

  62:     for (int i = 2; i<=a/2; i++)//从2一直往下试

  63:     {

  64:         count++;

  65:         while(a != i )

  66:         {

  67:             if (a%i == 0)

  68:             {

  69:                 a = a / i;

  70:                 x[count1] = i;

  71:                 count1++;

  72:                 count++;

  73:             }

  74:             else

  75:             {

  76:                 break;

  77:                 count++;

  78:             }

  79:         }

  80:     }

  81:     x[count1] = a;

  82:   // 将b分解质因数，并将质因数放入y数组中

  83:     for (int i = 2; i<=b/2; i++)//从2一直往下试

  84:     {

  85:          count++;

  86:         while(b != i )

  87:         {

  88:             if (b%i == 0)

  89:             {

  90:                 b = b / i;

  91:                 y[count2] = i;

  92:                 count2++;

  93:                  count++;

  94:             }

  95:             else

  96:             {

  97:                 break;

  98:             }

  99:         }

 100:     }

 101:     y[count2] = b;

 102:     int key = 0;

 103:     //在两个数组中寻找相同的元素的算法中，采取控制变量法，保持一个数组不变，用

 104:     //另一个数组中的每一个值与第二个数组中的值一个个比较，相同的保存到z中。

 105:    for (int m=0; m <= count1; m++)

 106:    {

 107:        key = x[m];

 108:         count++;

 109:        for (int n=0; n <= count2; n++)

 110:        {

 111:            if (key==y[n])

 112:            {

 113:                 count++;             

 114:                z[count3] = key;

 115:                count3++; 

 116:                break;

 117:            }

 118:        }

 119:    }

 120:    int max = 1;

 121:    for (int j = 0; j < count3; j++) //这里不要用 <= 不然，会出错。上面的count最后的数字有具体的值，此数组中对应的数据为0 

 122:    {

 123:        max = max * z[j];

 124:        count++;

 125:    }

 126:    cout << "采用分解质因数算法输出的结果是："<< endl;

 127:    cout << "输出最大公约数是："<< max << endl;

 128:    cout << "最大迭代次数是："<< count << endl;

 129:  }

 130:   

 131:   

 132:  int main()

 133:  {

 134:      while(1)

 135:  {

 136:      clock_t start,stop;

 137:      int a,b;

 138:      cout << "请输入所要求最大公约数的两个数值：" <<endl;

 139:      scanf("%d,%d",&a,&b);

 140:      if (a < b)

 141:      {

 142:         int temp = a;

 143:         a = b;

 144:         b = temp;

 145:      }

 146:      start = clock();

 147:      gcd1(a,b);

 148:      stop = clock();

 149:      cout << "执行时间是："<< stop - start << endl;

 150:   

 151:      start = clock();

 152:      gcd2(a,b);

 153:      stop = clock();

 154:      cout << "执行时间是："<< stop - start << endl;

 155:   

 156:      start = clock();

 157:      gcd3(a,b);

 158:      stop = clock();

 159:      cout << "执行时间是："<< stop - start << endl;

 160:  }

 161:      return 0;

 162:  }