The Euclidean algorithm – Find GCD (Greatest common divisor) in Java

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

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



Code:

 

Leave a Reply

Your email address will not be published. Required fields are marked *