俩个数最大公约数的C/C++实现

一.最大公因数求法：

  概念：俩个数的最大公约数是指能同时整除他们的最大正整数。
  
  辗转相除法(也称欧几里得算法)原理:
  设俩个数a,b(其中a>b)，求a,b的最大公约数gcd(a,b)步骤如下：
  【1】用较大的数处以较小的数，即a /b=q........r1(r1>=0);
  【2】若r1=0,则gcd(a,b)=b;
  【3】若r1！=0，则用b/r1=q............r2(r2>=0);
  【4】若.r2=0，则(a,b)=r1；
  【5】若r2！=0 ，则继续用r1/r2,.........,如此下去，直到整除为止；

其中最后一个余数为0的除数即为最大公约数gcd(a,b）。

公式：baud_freq = 16baud_rate / gcd(global_clock, 16baud_rate)的实现
tre

#include<iostream>

using namespace std;
int gcd_calc(int x,int y);

int main()
{
	unsigned_int  gcd_resylt;
	unsigned_int  baud_rate,baud_freq,global_clock;
	cout<<"enter baud rate"<<endl;
	cin>>buad_rate ;
	cout << "enter global clock" << endl;
	cin >> global_clock ;
	gcd_result = gcd_calc(global_clock,(16*buad_rate));
	buad_freq = (16*buad_rate)/gcd_result;
	cout << "buad_freq = "  << buad_freq << endl;
    cout << "gcd_result=" << gcd_result << endl;
    return 0
	}

int gcd_calc(int x, int y)
{
	int result =1;
    bool break_loop = false;
    int div;
    div =2;
    while (break_loop == false)
    {
        if ((x%div == 0) && (y%div ==0))
        {
        result = result*div;
        x=x/div;
        y=y/div;
        }
        else
        {
        div++;
        }
        if((div > x)|| (div > y))
        {
            break_loop = true;
        }
    }
    return result;
}

#include <iostream>

using namespace std;

//辗转相除法(欧几里得算法)

int gcd(int a, int b)
{
    int da = max(a,b);
    int xiao = min(a,b);
    if(da % xiao == 0)
        return xiao;
    else
        return gcd(xiao, da % xiao);

}

// 两个整数的最小公倍数等于两整数之积除以最大公约数

int lcm(int a, int b)
{
    return a*b / gcd(a, b);
}

int main() {
    int x, y;
    cout << "输入两个数字(按Ctrl+Z结束输入): ";
    while (cin >> x >> y)
        cout << "这两个数的最大公因数是：" << gcd(x, y) << endl
             << "这两个数的最小公倍数是：" << lcm(x, y) << endl;

流程图如下：

参考文章：
【1】opencores
【2】https://blog.csdn.net/zzzyyyyyy66/article/details/80188175