GCD of two numbers
Algorithm
Input Two integer a and b Output GCD of a and b. complexity O(d) where d is the number of digits in the smaller number gcd(a, b) 1 if (b = 0) then 2 Return a 3 else 4 Return gcd(b, a mod b)
Algorithm Description
Gcd () function takes two parameter a and b as an integer . If b=0 then gcd (Greatest common divisor) is a. If b is not zero then gcd function is recursively called until b become zero.
C Code
#include< stdio.h>
#include< conio.h>
int main()
{
int a,b,min,gcd,i;
printf("Enter two numbers ");
scanf("%d%d",&a,&b);
if(a
JAVA Code
import java.io.*;
class greatest_divisor{
public static int divisor(int x,int y)
{
int result;
if(y==0)
return x;
result=divisor(y,x%y);
return result;
}
}
class gcd
{
public static void main(String args[]) throws Exception
{
greatest_divisor g = new greatest_divisor();
int x,y;
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("enter the two numbers ");
x= Integer.parseInt(cin.readLine());
y= Integer.parseInt(cin.readLine());
if(x>y)
System.out.println("the GCD of "+x+" and "+y+" is "+g.divisor(x,y));
else
System.out.println("the GCD of "+x+" and "+y+" is "+g.divisor(y,x));
}
}
