不多说，直接粘程序：

1:  #include "stdafx.h"

2:  #include 
     

3:  using namespace  std;

4:  #include
     

5:  #include
     

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 << "请输入所要求最大公约数的两个数值：" <

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:  }

实验结果：

实验总结：

方法一当中，根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;

方法三当中，根据代码分解质因子算法O(n)=n²+n/2

但从我的实验结果来看，从时间复杂度来看，欧几里得算法的是最优算法，分解质因数算法其次，最后是连续整除法。从执行次数来看，欧几里得算法的是最优算法，连续整除法其次，最多的是分解质因数算法。再从代码运行的计数器和计算的时间来看，从执行次数上来分析，与理论分析结果一致，但从时间复杂度来看，结果不太一致。但我们可以得出结论的是：欧几里得算法最优。