博客

1、朴素法 2、更相减损算法 3、欧几里得算法（辗转相除法）

1、朴素法

①先判断两数a、b的大小，将较小值赋值给x

②判断a、b两数是否可以被x整除，可以，则输出x为最大公约数

③a、b不可以被x整除，则执行x-1，重复②③操作继续判断

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,x;
	cin >> a >>b;
	x = min(a,b);
	while(x>1 && (a%x!=0 || b%x!=0))
        	x--;
	cout << x <<endl;
	return 0;
}

2、更相减损法

①判断a,b两数是否是偶数，如果是就同时除以二

②一直除到有一方为奇数，或者两个都是奇数时，比较a,b大小，用大数减去小数，判断差和小数是否相等，如果不等，则继续用大数减小数

③如果差和减数相等，最大公约数=相等的数*(2^除以二的次数）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b, num=0,t;
    cin >> a >> b;
    if (a == b){
        cout << a << endl;
        return 0;
    }
    t=a,a = max(a, b), b = min(t, b);
    while ((a % 2 == 0) && (b % 2 == 0))
        a /= 2, b /= 2, num++;
    while (b != a - b)
        t=a-b,a = max(b, t), b = min(b, t);
    cout << b * (1<<num) << endl;
    return 0;
}

3、辗转相除法（欧几里得算法）降低了复杂度

①对a,b做求余（求模）运算，判断余数r1是否等于零

②r = 0,则a,b的最大公约数为b

③r != 0,则把之前b的值赋值给a，r的值赋值给b，再求一次余数，判断余数r，重复②③操作，直到r为零为止，此时的b就是最大公约数

#include<iostream>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    int r = a%b;
    while (r!=0){
        a = b;
        b = r;
        r = a%b;
    }
    cout<<b<<endl;
    return 0 ;
}