# GCD and LCM
---
# GCD
## 最大公因數
----
```cpp=
int GCD(int a, int b){ // a >= b
int gcd = 1;
for(int i = 1; i <= b; i++){
if(a%i == 0 && b%i == 0) gcd = i;
}
return gcd;
}
```
----
```cpp=
int GCD(int a, int b){ // a >= b
if(b == 0) return a;
return GCD(b, a%b);
}
```
----
| a | b |
| --- | --- |
| 12 | 8 |
| 8 | 4 |
| 4 | 0 |
---
# LCM
#### ~~液晶監視器（Liquid Crystal Monitor）~~
## 最小公倍數
----
```cpp=
int LCM(int a, int b){ // a >= b
int lcm = a;
for(int i = a; i <= a*b; i++){
if(i%a == 0 && i%b == 0){
lcm = i;
break;
}
}
return lcm;
}
```
----
```cpp=
int GCD(int a, int b){ // a >= b
if(b == 0) return a;
return GCD(b, a%b);
}
int LCM(int a, int b){ // a >= b
return a*b / GCD(a, b);
}
```
{"metaMigratedAt":"2023-06-15T02:59:22.791Z","metaMigratedFrom":"YAML","title":"GCD and LCM","breaks":true,"contributors":"[{\"id\":\"e9395e03-a75e-451d-8392-22ff7e9c3ef5\",\"add\":884,\"del\":38}]"}