---
# System prepended metadata

title: GCD and LCM
tags: [' 資讀', ckcsc]

---

---
tags: ckcsc, 資讀
---

# 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);
}
```