GCD of two numbers | Program to find the GCD or HCF of two numbers

Program to find the GCD of two numbers is discussed here. The HCF (Highest Common Factor or GCD (Greatest Common Divisor) of two integers is nothing but the largest integer that can exactly divide a given number without leaving a remainder.

gcd of two numbers

GCD of two numbers 

#include<stdio.h>
#include<stdlib.h>
int main()
{
int a,b,gcd;
printf(“\nEnter two numbers : “);
scanf(“%d %d”,&a,&b);
int i;
for(i = 1; i <= a && i <= b; i++)
{
if((a % i == 0) && (b % i == 0))
{
gcd = i;
}
}
printf(“\nGCD of %d and %d is %d “,a,b,gcd);
printf(“\n”);
return 0;
}

#include<iostream>
using namespace std;
int main()
{
int a,b,gcd;
cout <<“\nEnter two numbers : “;
cin >> a >> b;
int i;
for(i = 1; i <= a && i <= b; i++)
{
if((a % i == 0) && (b % i == 0))
{
gcd = i;
}
}
cout << “\nGCD of “<< a << ” and ” << b << ” is ” << gcd;
cout << endl;
return 0;
}

import java.util.*;
public class Main
{
public static void main(String[] args)
{
int a,b,gcd = 0;
System.out.print(“\nEnter two numbers : “);
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
int i;
for(i = 1; i <= a && i <= b; i++)
{
if((a % i == 0) && (b % i == 0))
{
gcd = i;
}
}
System.out.println(“\nGCD of ” + a + ” and ” + b + ” is ” + gcd);
System.out.println();
}
}

gcd = 0
print(“Enter two numbers : “)
a = int(input())
b = int(input())
i = 1
     while(i <= a and i <= b):
          if((a % i == 0) and (b % i == 0)):
               gcd = i
          i = i + 1

print(“GCD : “,end=”);
print(gcd)

GCD of two numbers using recursion

#include <stdio.h>

int gcd(int a, int b)
{
if (b != 0)
return gcd(b, a % b);
else
return a;
}

int main()
{
int a, b;
printf(“Enter two numbers: “);
scanf(“%d %d”, &a, &b);

printf(“\nGCD of %d and %d is %d\n”, a, b, gcd(a,b));
return 0;
}

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
if (b != 0)
return gcd(b, a % b);
else
return a;
}

int main()
{
int a, b;
cout << “Enter two numbers: “;
cin >> a >> b;
cout << “\nGCD of ” << a << ” and ” << b << ” is ” << gcd(a,b);
cout << endl;
return 0;
}

import java.util.*;
public class Main
{
static int gcd(int a, int b)
{
if (b != 0)
return gcd(b, a % b);
else
return a;
}

public static void main(String[] args)
{
int a,b,gcd = 0;
System.out.print(“\nEnter two numbers : “);
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
System.out.println(“\nGCD of ” + a + ” and ” + b + ” is ” + gcd(a,b));
System.out.println();
}}

def gcd(a, b):
     if (b != 0):
          return gcd(b, a % b)
     else:
          return a

print(“Enter two numbers : “)
a = int(input())
b = int(input())

gcd = gcd(a,b)
print(“GCD : “,end = “”);
print(gcd)

GCD of two numbers using Command Line Arguments

#include<stdio.h>
int main(int x, char *y[])
{
inta,b,small,i;
a=atoi(y[1]);
b=atoi(y[2]);
small=a>b?b:a;
for(i=small;i>=1;i–)
{
if((a%i==0)&&(b%i==0))
{
printf(“%d”,i);
break;
} }
return 0;
}