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