Write a program to find GCD of given two numbers using Euclid’s algorithm. Information and Network Security (2170709) GTU

Algorithm/Steps:

1. First of all take two numbers from the user as input.

2. In the above example consider a and b as given

3. Now divide the greater number by smaller .The remainder we get from it should be

again dividing the divisor that we have previously divided.

4. a/b gives a remainder of r

    b/r gives a remainder of s

    r/s gives a remainder of t

    ..........

    w/x gives a remainder of y

    x/y gives no remainder

Code:

import java.util.*;

public class GCD {

            public static void main(String args[])

            {

                        Scanner sc = new Scanner(System.in);

                        System.out.println("Enter first number");

                        int a = sc.nextInt();

                        System.out.println("Enter second number");

                        int b = sc.nextInt();

                        int temp;

                        do

                        {

                                    temp=a%b;

                                    a=b;

                                    b=temp;

                        }while(temp!=0);

                        System.out.println(a);

            }

}