【蓝桥杯试题 练习题 最大公约数】

【问题描述】

给定两个正整数，求他们的最大公约数。

【输入格式】

输入一行，包含两个正整数（<1000000000）

【输出】

一个整数，两个正整数的最大公约数。

【范例】

6 9

3

法1：最常规

//最大公约数

#include<iostream>

using namespace std;

int main()
{
    int num1, num2, maxGY;

    cin >> num1 >> num2;
    

    if (num2 > num1)
    {
       for (int i = 2; i <= num2; i++)
        {
            if (num1 % i == 0 & num2 % i== 0)
            {
                if (i > maxGY)
                {
                    maxGY = i;
                }
            }
        }
    }
    else
    {
       for (int i = 2; i <= num1; i++)
        {
            if (num1 % i == 0 & num2 % i== 0)
            {
                if (i > maxGY)
                {
                    maxGY = i;
                }
            }
        }
    }

    cout << maxGY << endl;

    return 0;
}

法二：辗转相除

#include <bits/stdc++.h>
using namespace std;
int GCD(int a,int b)
{
	if(a%b==0)
		return b;
	GCD(b,a%b);
}
int main()
{
	int m,n;
	cin>>m>>n;
	cout<<GCD(m,n);
}