算法如功夫——C++输入两个数求它们的最大公约数

77 阅读 0 评论 51 点赞

我是靠谱客的博主明亮裙子，最近开发中收集的这篇文章主要介绍算法如功夫——C++输入两个数求它们的最大公约数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法如功夫，套路练久了，才能应用自如！

学功夫不能死练，知其所以然，取长补短！

#include <iostream>

using namespace std;

int gcd( int a, int b )

{

int rem;

while ( b )

{

rem = a % b;

a = b;

b = rem;

}

return a;

}

int main( )

{

int a, b;

cout << "请输入2个数：";

cin >> a >> b;

cout << "最大公约数为：" << gcd( a, b );

return 0;

}

例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：

其中“a mod b”是指取 a ÷ b 的余数。
a  b  a mod b
123456  7890  5106
7890  5106  2784
5106  2784  2322
2784  2322  462
2322  462  12
462  12  6
12  6  0
只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。
辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。