Tutorial Playlist
191 Lessons1. Introduction to Java
2. What is Java?
3. History of Java
4. Java Tutorial for Beginners
5. How Do Java Programs Work?
6. JDK in Java
7. C++ Vs Java
8. Java vs. Python
9. Java vs. JavaScript
10. From Java Source Code to Executable
11. How to Install Java in Linux
12. How to Install Java in Windows 10
13. Java Hello World Program
14. Structure of Java Program and Java Syntax
15. Operators in Java
16. Java If-else
17. Switch Case In Java
18. Loops in Java
19. Infinite loop in Java
20. For Loop in Java
21. For Each Loop in Java
22. Constructor in Java
23. Constructor Overloading in Java
24. Copy Constructor in Java
25. Default Constructor in Java
26. Parameterized Constructors in Java
27. Constructor Chaining In Java
28. Finalize Method in Java
29. Static Method in Java
30. Equals Method in Java
31. Abstract Method in Java
32. toString() Method in Java
33. Difference between equals method in Java
34. Inheritance in Java
35. Multiple Inheritance in Java
36. Hierarchical Inheritance in Java
37. Java Classes and Objects
38. Scanner Class in java
39. All classes in java are inherited from which class
40. What is Nested Class in Java
41. POJO Class in Java
42. Anonymous Class in Java
43. Final Class in Java
44. Object Class in Java
45. Packages in Java
46. Access Modifiers in Java
47. Static Keyword In Java
48. Final Keyword in Java
49. Checked and Unchecked Exceptions in Java
50. User Defined Exception in Java
51. Error vs. Exception in Java
52. Java Collection
53. Collections in Java
54. Garbage Collection in Java
55. Generics In Java
56. Java Interfaces
57. Functional Interface in Java
58. Marker Interface in Java
59. Streams in Java
60. Byte stream in java
61. File Handling in Java
62. Thread in Java
63. Thread Lifecycle In Java
64. Daemon Thread in Java
65. Thread Priority in Java
66. Deadlock in Java
67. String Pool in Java
68. Java Database Connectivity(JDBC)
69. Design Patterns in Java
70. Functional Programming in Java
71. OOP vs Functional vs Procedural
72. Heap Memory and Stack Memory in Java
73. Applet in Java
74. Java Swing
75. Java Frameworks
76. Hibernate Framework
77. JUnit Testing
78. How to Install Eclipse IDE for Java?
79. Command line arguments in Java
80. Jar file in Java
81. Java Clean Code
82. OOPs Concepts in Java
83. Java OOPs Concepts
84. Overloading vs Overriding in Java
85. Java 8 features
86. String in Java
87. String to int in Java
88. Why String Is Immutable in Java?
89. Primitive Data Types in Java
90. Non-Primitive Data Types in Java
91. This and Super Keyword in Java
92. HashMap in Java
93. Comparable And Comparator in Java
94. Type Casting in Java
95. Arrays Sort in Java with Examples
96. Variable Hiding and Variable Shadowing in Java
97. Enum in Java
98. Substring in Java
99. Pattern Programs in Java
100. Hashcode in Java
101. What is ByteCode in Java?
102. How To Take Input From User in Java
103. GCD of Two Numbers in Java
Now Reading
104. Linked List in Java
105. Arithmetic Operators in Java
106. Conditional Operators in Java
107. Stack and Queue in Java
108. Array Length in Java
109. Number Pattern Program in Java
110. Split in java
111. Map In Java
112. Difference Between Throw and Throws in Java
113. Difference Between Data Hiding and Abstraction
114. HashSet in Java
115. String Length in Java
116. Factorial Using Recursion in Java
117. DateFormat in Java
118. StringBuilder Class in java
119. Instance variables in Java
120. Java List Size
121. Java APIs
122. Reverse an Array in Java
123. StringBuffer and StringBuilder Difference in Java
124. Java Program to Add Two Numbers
125. String to Array in Java
126. Regular Expressions in Java
127. Identifiers in Java
128. Data Structures in Java
129. Set in Java
130. Pass By Value and Call By Reference in Java
131. Try Catch in Java
132. Bubble Sort in Java
133. Caesar Cipher Program in Java
134. Queue in Java
135. Object Creation in Java
136. Multidimensional Array in Java
137. How to Read a File in Java
138. String Comparison in Java
139. Volatile Keyword in Java
140. Control Statements in Java
141. Jagged Array in Java
142. Two-Dimensional Array in Java
143. Java String Format
144. Replace in Java
145. charAt() in Java
146. CompareTo in Java
147. Matrix Multiplication in Java
148. Static Variable in Java
149. Event Handling in Java
150. parseInt in Java
151. Java ArrayList forEach
152. Abstraction in Java
153. String Input in Java
154. Logical Operators in Java
155. instanceof in Java
156. Math Floor in Java
157. Selection Sort Java
158. int to char in Java
159. Stringtokenizer in java
160. Implementing and Manipulating Abs in Java
161. Char array to string in java
162. Convert Double To String In Java
163. Deque in Java
164. Converting a List to an Array in Java
165. The Max function in java
166. Removing whitespace from string in java
167. String arrays in Java
168. Strings in Java Vs Strings in Cpp
169. Sum of digits of a number in Java
170. Art of Graphical User Interfaces
171. Trim in Java
172. RxJava
173. Recursion in Java
174. HashSet Java
175. Difference Between Java and Python
176. Square Root in Java
177. Reverse A String in Java
178. Even Odd Program in Java
179. Fibonacci Series in Java
180. Prime Number Program in Java
181. Java Program to Print Prime Numbers in a Given Range
182. Java Leap Year Program
183. Swapping of Two Numbers in Java
184. LCM of Two Numbers in Java
185. Math.sqrt() Function in Java
186. Area of Triangle in Java
187. Sort a String In Java
188. Factorial Program in Java
189. Javafx
190. Lambda expression in java
191. Setup Java Home and IDE on macOS
The greatest common divisor (GCD) or greatest common factor (GCF) is the highest possible divisor of two or more numbers.
To find out the GCD for different sets of numbers manually is a tedious process. However, finding GCD for two numbers in Java is pretty straightforward.
A Java program to determine the GCD of two or more numbers has multiple applications in various domains, such as cryptography, data encryption, and algorithm design.
Right from the basic Java loops to determine the GCD to the Euclidean algorithm, this tutorial aims at indulging you in all the concepts related to calculating the GCD of two numbers in Java.
To find the Greatest Common Factor manually, you must first separate each number in the set. So how to find the GCD of two numbers?
For example, 18 and 27.
Now list the factors of these numbers.
Factors of 18: 1, 2, 3, 6, 9, 18
Factors of 27: 1, 3, 9, 27
Now identify the common factors of the lot. They are 1, 3, and 9. Of these, 9 is the greatest number. Hence the GCD of 18 and 27 is 9.
The process is similar to finding the GCD of n numbers in Java, where n is any number greater than 1.
For example, 21, 42, and 54.
Factors of 21: 1, 3, 7, 21
Factors of 42: 1, 2, 3, 6, 7, 14, 21, 42
Factors of 54: 1, 2, 3, 6, 9, 18, 27, 54
Now identifying the common factors: 1, 3.
So the GCD of 21, 42, and 54 is 3.
Here are some different methods you can use to find the GCD of two numbers:
Loops in Java are repetitive paradigms that run under conditions specified by the user. There are three major kinds of loops in Java:-
i) “for” loop
ii) “while” loop
iii) “do-while” loop
The user can also define a customized method within the class to calculate the GCD.
The Euclidean algorithm is one of the most effective ways of finding the GCD of two numbers. The algorithm works under the following conditions:
1. Suppose the two numbers whose GCD we are supposed to find out are x and y.
2. If x=0, method GCD(x,y) = y, and the syntax returns y as the GCD.
3. If y=0, method GCD(x,y) = x, and the syntax returns x as the GCD.
4. Now if neither x nor y equals 0, the algorithm proceeds to the long division method where Q is the quotient and R is the remainder.
5. x= Qy + R.
6. Now find GCD (y, R) using the above steps again until one of them becomes 0.
Using the modulo operator simplifies finding the GCD, determining whether one number is divisible by another without explicitly dividing them. We can efficiently find the GCD of the two numbers by repeatedly applying the modulo operation and updating the values.
You can follow these steps to find the GCD of two numbers in Java using the modulo operator:
1. Start with two given numbers: x and y.
2. Take the modulo (remainder) of x divided by y using the % operator.
3. Set x equal to y, and y equal to R obtained in the previous step.
4. Repeat the steps until the remainder is 0.
5. Once the remainder becomes 0, the last non-zero remainder obtained will be the GCD of the two numbers.
Here is a program to find the GCD of two numbers that will help you understand the use of the “for” loop:
public class GCDExample {
public static void main(String[] args) {
int number1 = 36;
int number2 = 48;
int gcd = 1;
// Find the smaller number between number1 and number2
int smallerNumber = (number1 < number2) ? number1 : number2;
// Iterate from 1 to the smaller number
for (int i = 1; i <= smallerNumber; i++) {
// Check if both number1 and number2 are divisible by i
if (number1 % i == 0 && number2 % i == 0) {
gcd = i; // Update gcd
}
}
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
}
}
In this example, we have the same numbers, number1, and number2, whose GCD must be found. The gcd variable is initialized to 1.
Similar to the previous example, we find the smaller number between number1 and number2 using the ternary operator and assign it to the smallerNumber variable.
Next, we initialize a variable i to 1 before entering the while loop. Within the loop, we check if number1 and number2 are divisible by i. If they are, we update the gcd variable to i. After that, we increment i by 1 using i++.
The loop continues until i exceeds the smallerNumber value. Once the loop terminates, we print the GCD of the two numbers using the System.out.println() statement.
Here is a program to find the GCD of two numbers to help you understand the use of the “while” loop:
public class GCDExample {
public static void main(String[] args) {
int number1 = 36;
int number2 = 48;
int gcd = 1;
// Find the smaller number between number1 and number2
int smallerNumber = (number1 < number2) ? number1 : number2;
int i = 1;
while (i <= smallerNumber) {
// Check if both number1 and number2 are divisible by i
if (number1 % i == 0 && number2 % i == 0) {
gcd = i; // Update gcd
}
i++; // Increment i
}
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
}
}
In this example, we have numbers number1 and number2, which may be positive or negative. We want to find the GCD of these numbers.
First, we find the absolute values of number1 and number2 using the Math.abs() method, which returns the positive value of a number.
Then, we call the findGCD() method with the absolute values of the numbers. This method uses the Euclidean algorithm to find the GCD of two numbers recursively.
The findGCD() method takes two parameters, number1 and number2. If number2 is 0, we have found the GCD, so we return number1. Otherwise, we recursively call findGCD() with number2 and number1 % number2.
Finally, we print the GCD of the original numbers (taking into account their signs) using the System.out.println() statement.
We can use the absolute values of the numbers to find the GCD of both positive and negative numbers. Here's an example:
public class GCDExample {
public static void main(String[] args) {
int number1 = -36;
int number2 = 48;
// Find the absolute values of the numbers
int absNumber1 = Math.abs(number1);
int absNumber2 = Math.abs(number2);
int gcd = findGCD(absNumber1, absNumber2);
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
}
// Recursive method to find GCD using Euclidean algorithm
public static int findGCD(int number1, int number2) {
if (number2 == 0) {
return number1;
}
return findGCD(number2, number1 % number2);
}
}
Here is another example of GCD of two numbers using the user-defined method:
import java.util.Scanner;
public class GCDExample {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the first number: ");
int number1 = scanner.nextInt();
System.out.print("Enter the second number: ");
int number2 = scanner.nextInt();
int gcd = findGCD(number1, number2);
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
scanner.close();
}
// User-defined method to find GCD using Euclidean algorithm
public static int findGCD(int number1, int number2) {
if (number2 == 0) {
return number1;
}
return findGCD(number2, number1 % number2);
}
}
In this example, we use the Scanner class to accept input from the user. The user is prompted to enter the two numbers.
We then call the findGCD() method and pass the input numbers to it. This method uses the Euclidean algorithm to find the GCD of two numbers recursively.
The findGCD() method takes two parameters, number1 and number2. If number2 is 0, we have found the GCD, so we return number1. Otherwise, we recursively call findGCD() with number2 and number1 % number2.
Finally, we print the GCD of the entered numbers using the System.out.println() statement.
Here is an example of the GCD of two numbers using the Euclidean algorithm:
public class GCDExample {
public static void main(String[] args) {
int number1 = 36;
int number2 = 48;
int gcd = findGCD(number1, number2);
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
}
// Method to find GCD using Euclidean algorithm
public static int findGCD(int number1, int number2) {
while (number2 != 0) {
int temp = number2;
number2 = number1 % number2;
number1 = temp;
}
return number1;
}
}
We use the Euclidean algorithm to find the GCD. The algorithm repeatedly divides the larger number by the smaller number and updates the values until the remainder becomes 0.
We use a while loop in the findGCD() method to perform the division and updates. We store the value of number2 in a temporary variable temp before updating it with the remainder of the division (number1 % number2). We update number1 with the value of temp. This process continues until number2 becomes 0.
Here is another example of GCD of two numbers using the recursion:
public class GCDExample {
public static void main(String[] args) {
int number1 = 36;
int number2 = 48;
int gcd = findGCD(number1, number2);
System.out.println("The GCD of " + number1 + " and " + number2 + " is " + gcd);
}
// Recursive method to find GCD
public static int findGCD(int number1, int number2) {
if (number2 == 0) {
return number1;
}
return findGCD(number2, number1 % number2);
}
}
The findGCD() method takes two parameters, number1 and number2. If number2 is 0, we have found the GCD, so we return number1. Otherwise, we recursively call findGCD() with number2 and number1 % number2, representing the remainder when number1 is divided by number2.
The recursion continues until the base case is reached, where number2 becomes 0, and the GCD is returned.
The GCD is a powerful tool in many computational problems, and being able to calculate it accurately and efficiently is crucial. Whether you are working on algorithms, number theory, or cryptography, the knowledge you have gained in this tutorial will prove valuable.
Now that you have a solid understanding of the GCD, we encourage you to practice implementing it in Java and explore its applications in different programming scenarios. You can also find the GCD of two numbers in C or the GCD of two numbers in Python. By building upon this knowledge and exploring further, you can continue to expand your programming skills and problem-solving abilities.
1. Is it possible to calculate LCM after calculating the GCD of two numbers in Java?
Yes, it is possible to calculate the GCD and LCM of two numbers in Java simultaneously in the same class. To calculate the LCM using the GCD in Java, you can utilize the following formula:
LCM = (x * y) / GCD [x and y being the two numbers whose GCD has been determined]
2. How to calculate the GCD of two numbers in Python?
Python allows calculating the GCD of two numbers using special math.gcd() function. The function returns the GCD of the given numbers.
3. What is the GCD Java library?
In Java, no specific "GCD Java library" is dedicated solely to calculating the Greatest Common Divisor (GCD) of two numbers. However, Java does provide a built-in mathematical class called java.lang.Math, which offers a method for computing the GCD.
The java.lang.Math class includes a static method named gcd(), which calculates the GCD of two integers. The method takes two int arguments and returns their GCD as a positive integer.
PAVAN VADAPALLI
Director of Engineering
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working …Read More
Popular
Talk to our experts. We’re available 24/7.
Indian Nationals
1800 210 2020
Foreign Nationals
+918045604032
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enrolling. upGrad does not make any representations regarding the recognition or equivalence of the credits or credentials awarded, unless otherwise expressly stated. Success depends on individual qualifications, experience, and efforts in seeking employment.
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...