Euclid's Algorithm

For two positive integers

Algorithm (using recursion)

function gcd(a, b)

  if b = 0 return a
  else return gcd(b, a mod b)

Program

import java.io.*;
public class Euclid{
  public static int gcd(int a,int b){
  if (b == 0) 
  return a;
  else 
  return gcd(b, a%b);
  } 
  public static void main(String[] args){  
  try{
   
  BufferedReader object=new BufferedReader  
  (new InputStreamReader(System.in));
  
  System.out.print("input a:");
  String x=object.readLine();  
  System.out.print("input b:");
  String y=object.readLine();  
  int a = Integer.parseInt(x);
  int b = Integer.parseInt(y);  
  System.out.println("gcd(" + a + ", " + b + ") = " + gcd(a,b));  
  }
  catch(Exception e){}
  }
 
}

For three positive integers

Algorithm (using iteration)

function gcd(a, b)
  while b ≠ 0
  t := b
  b := a mod b
  a := t
  return a

Program

import java.io.*;
public class Euclid2{
  public static int gcd(int p, int q) {
  while (q != 0) {
  int temp = q;
  q = p % q;
  p = temp;
  }
  return p;
  }  
  public static void main(String args[]){  
  try{  
  BufferedReader object=new BufferedReader  
  (new InputStreamReader(System.in));
   
  System.out.print("input a:");
  String x=object.readLine();  
  System.out.print("input b:");
  String y=object.readLine();
  System.out.print("input c:");
  String z=object.readLine();
   
  int a = Integer.parseInt(x);
  int b = Integer.parseInt(y);
  int c = Integer.parseInt(z);  
  int r1 = gcd(a, b);
  int r2 = gcd(c,r1);  
  System.out.println("gcd = " + r2);
  }  
  catch(Exception e){}
  }
}