辗转相除法（最大公因数 最小公倍数）算法_辗转相除法模板

//2019 12 20 辗转相除法模板

#include <iostream>
int isprime(int n);
using namespace std;
int main()
{
	int n, m;
	int a, b;
	cin >> n;//表示n组案例
	for (int i = 0; i <n; i++)
	{
		int count = 0;
		int yushu = 1;
		cin >> a >> b;
		if (a>b)
		{
			swap(a, b);
		}
		while (1)//辗转相除法
		{
			yushu = b%a;
			if (yushu == 0)
			{
				cout << a;
				break;
			}
			b = a;
			a = yushu;			
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void acg(int a,int b	)
{
if(b==0{return a;}
 return acg(b,a%b);
}
1
2
3
4
5

最小公倍数十分好求
两数相乘/最大公因数