This algorithm finds gcd by performing repeated division starting from the two numbers we want to find the gcd of **until we get a remainder of**

- If
then , since the , and we can stop - If
then , since the , and we can stop - Write
in quotient remainder form - Find
, using the Euclidean Algorithm since

**Example**

**C++**

```
int gcd(int a,int b) {
int swap;
while ((a % b) > 0) {
swap = a % b;
a = b;
b = swap;
}
return b;
}
```