The Greatest Common Divisor (GCD) is a fundamental mathematical concept used in various applications. In this blog, we will explore the importance of finding the GCD of two numbers and its practical applications.
What is the GCD of Two Numbers in Java?
In the realm of number theory, the Greatest Common Divisor (GCD) holds great importance. It refers to the largest positive integer that divides two or more numbers without leaving any remainder. The GCD plays a pivotal role in various mathematical concepts and computations.
The properties of the GCD provide valuable insights into its behavior. One such property is divisibility. If a number divides both given numbers, it will also divide their GCD. Moreover, the GCD can be expressed as a combination of the numbers’ prime factorization, allowing for efficient calculations.
Euclidean Algorithm:
The Euclidean Algorithm is a fundamental technique for finding the GCD of two numbers. Named after the ancient Greek mathematician Euclid, this algorithm follows a straightforward iterative process.
To apply the Euclidean Algorithm, we repeatedly divide the larger number by the smaller number and replace the larger number with the remainder obtained. This process continues until the remainder becomes zero. The last non-zero remainder obtained in this sequence is the GCD of the original two numbers.
Also, learn about Swap of Two Numbers in Java, Now!
How to find the Greatest Common Factor:
To determine the Greatest Common Factor (GCF) of two numbers, you can follow these steps:
1. Identify and list all the factors of each number.
2. Find the factors that are common to both numbers.
3. Choose the greatest number among the common factors as the GCF.
Find GCD of Two Numbers Using Java for loop
//GCD of Two Numbers in Java
import java.util.*;
public class FindGCDEx1
{
public static void main(String[] args)
{
//x and y are the numbers to find the GCF
int a = 80, b = 70, gcd = 1;
//running loop form 1 to the smallest of both numbers
for(int i = 1; i <= a && i <= b; i++)
{
//returns true if both conditions are satisfied
if(a%i==0 && b%i==0)
//storing the variable i in the variable gcd
gcd = i;
}
//prints the gcd
System.out.printf("GCD of %d and %d is: %d", a, b, gcd);
}
}
Output:
GCD of 80 and 70 is: 10Know the nth Prime Number in Java here!
Find GCD of Two Numbers Using Java while Loop
//GCD of Two Numbers in Java
import java.io.*;
public class FindGCDEx2
{
public static void main(String[] args)
{
int a=28, b=54;
while(a!=b)
{
if(a>b)
a=a-b;
else
b=b-a;
}
System.out.printf("GCD of a and b is: " +b);
}
}
Get Complete Python Interview Questions and Answers, here!
Output:
GCD of a and b is: 2Find GCD of Two Numbers Using User-Defined Method
//GCD of Two Numbers in Java
import java.util.Scanner;
public class FindGCDEx4
{
//private static Scanner sc;
public static void main(String[] args)
{
int m, n, gcd = 0;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the First Number: ");
m = sc.nextInt();
System.out.print("Enter the Second Number: ");
n = sc.nextInt();
gcd = findGCD(m, n);
System.out.println("GCD of " + m + " and " + n + " = " + gcd);
}
public static int findGCD(int x, int y)
{
while(y != 0)
{
if(x > y)
{
x = x - y;
}
else
{
y = y - x;
}
}
return x;
}
}
Output:
Enter the First Number: 45
Enter the Second Number: 80
GCD of 45 and 80 = 5Find GCD of Two Numbers Using the Euclidean Algorithm
//GCD of Two Numbers in Java
import java.util.Scanner;
public class FindGCDEx5
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the two numbers: ");
int m = sc.nextInt();
int n = sc.nextInt();
System.out.println("The GCD of two numbers is: " + findGCD(m,n));
}
static int findGCD(int m, int n)
{
int r=0, a, b;
a = (m > n) ? m : n; // a is greater number
b = (m < n) ? m : n; // b is smaller number
r = b;
while(a % b != 0)
{
r = a % b;
a = b;
b = r;
}
return r;
}
}
Output:
Enter the two numbers:
465
145
The GCD of two numbers is: 5Find GCD of Two Numbers Using Modulo Operator
//GCD of Two Numbers in Java
import java.util.Scanner;
public class FindGCDEx6
{
public static void main(String[] args)
{
int x = 102, y = 345;
System.out.println("GCD of " + x +" and " + y + " is " + findGCD(x, y));
}
//recursive function to return gcd of a and b
static int findGCD(int x, int y)
{
if (y == 0)
return x;
return findGCD(y, x % y);
}
}
Output:
GCD of 102 and 345 is 3In conclusion, the Greatest Common Divisor (GCD) is a crucial concept in mathematics with various practical applications. In Java, there are multiple approaches to find the GCD of two numbers, such as using loops, the Euclidean algorithm, user-defined methods, or the modulo operator. Understanding and utilizing the GCD allows us to solve complex mathematical problems efficiently and explore its implications in different fields.
We hope that our blog post on “GCD of Two Numbers in Java” will effectively guide and inform you about your Java-related queries.To keep enhancing your coding skills, do check out Newtum’s website and explore our online coding courses covering Java, html, PHP, and more.
About The Author
