This article explains Euclidean algorithm from programming perspective. For Proof of Euclidean algorithm refer Wikipedia

### Problem

Find GCD of 66 & 42

### Steps as per Euclidean Algorithm

- 66 =
**42*** 1 +**24**–> (Find reminder of 66 & 42) **42**=**24*** 1 +**18**–> (Find reminder of earlier divider 42 & earlier reminder 24)**24**=**18*** 1 +**6**–> (Find reminder of earlier divider 24 & earlier reminder 18)**18**=**6*** 3 + 0 –> (Find reminder of earlier divider 18 & earlier reminder 6. Reminder zero so stop. Current divider 6 is the GCD !)

### Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Euclidean Algorithm public class FindGcd{ public static void main(String... args){ new FindGcd().gcd(66,24); } public void gcd(int a, int b){ int rem = b; while(rem != 0){ rem = a % b; a = b; // Earlier divider becomes a b = rem; // Earlier reminder becomes b } // Final divider which was saved in a is GCD. System.out.println("GCD = " + a); } } |