$show=/label

Java Program to Find GCD of Two Numbers

SHARE:

A quick java practical guide and program to find GCD of Two Numbers GCD means Greatest Common Divisor.

1. Introduction


In this tutorial, We will learn how to calculate the GCD for a given two numbers. GCD means Greatest Common Divisor.

The GCD of two numbers is the largest positive integer number that divides both the numbers without leaving any remainder (remainder should be 0). In some of the cases, GCD is called the Highest Common Factor (HCF).

Let us take an example GCD of 60, 90 is 30.


Factors of a number 60 : 2 * 2 * 3 * 5
Factors of a number 90 : 2 * 3 * 3 * 5

Common unique factors are: 2, 3, 5

Multiplication of common factors = 2 * 3 * 5 = 30

This can be done in two approaches.

A) Running the loop till the minimum of two numbers
B) GCD finding using the subtraction method.

These two methods are implemented without using a recursive approach.

Java Program to Find GCD of Two Numbers




2. Running a for loop till a minimum of two numbers


In this approach, we will first find the minimum of two numbers using Math.min(a, b) method which returns the min number and will run the for loop till min number.

package com.java.w3schools.blog.java.program.to;

import java.util.Scanner;

/**
 * 
 * Java Program to Find GCD of Two Numbers using and Running a for loop till
 * minimum of two numbers
 * 
 * @author JavaProgramTo.com
 *
 */
public class GCDForLoop {

 public static void main(String[] args) {

  System.out.println("Enter a first number : ");
  Scanner scanner = new Scanner(System.in);
  int first = scanner.nextInt();

  System.out.println("Enter a second number : ");
  int second = scanner.nextInt();

  // executing a for loop till min of two numbers.

  int min = Math.min(first, second);
  int gcd = 1;
  for (int i = 1; i <= min; i++) {

   if (first % i == 0 && second % i == 0) {
    gcd = i;
   }
  }

  System.out.println("GCD of two numbers (" + first + ", " + second + ") is : " + gcd);

 }

}

Output:

Enter a first number : 60
Enter a second number : 90
GCD of two numbers (60, 90) is : 30

3. Using Subtraction method


We will be using a while loop with subtraction logic. This is a very simple logic and efficient one. Here, we will be subtracting from the larger number and smaller number untill both numbers becomes the same. In the end, the second number will be the minimum number which will be the GCD of those two numbers.

Printing prime numbers with while loop example program
package com.java.w3schools.blog.java.program.to;

import java.util.Scanner;

/**
 * 
 * Java Program to Find GCD of Two Numbers Using Subtraction method
 * 
 * @author JavaProgramTo.com
 *
 */
public class GCDSubstractMethod {

 public static void main(String[] args) {

  System.out.println("Enter a first number : ");
  Scanner scanner = new Scanner(System.in);
  int first = scanner.nextInt();

  System.out.println("Enter a second number : ");
  int second = scanner.nextInt();

  while (first != second) {

   if (first > second) {
    first = first - second;
   } else {
    second = second - first;
   }
  }

  System.out.println("GCD : " + second);
 }

}

Output:

Enter a first number : 50
Enter a second number : 120
GCD : 10

4. Possible Exceptions


If you do not handle the for loop properly and if you do divide the number with 0 then you will end up in the following exception.

Exception in thread "main" java.lang.ArithmeticException: / by zero
 at com.java.w3schools.blog.java.program.to.GCDForLoop.main(GCDForLoop.java:30)

5. Conclusion


In this article, We have seen how to find the GCD of two numbers in java using two methods. The first approach is to run a for loop till a minimum of two numbers and the second approach is using while loop with subtract method.
The second method is most suitable with higher number input values and most efficient method.



COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,16,Arrays,7,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,5,Collections,22,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,81,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,4,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,3,Fast,1,Files,9,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,29,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,Java 8,66,Java 8 Difference,2,Java 8 Stream Conversions,2,java 8 Stream Examples,3,Java 9,1,Java Conversions,11,Java Design Patterns,1,Java Files,1,Java Program,2,Java Programs,65,java.lang,5,java.util. function,1,jQuery,1,Kotlin,10,Kotlin Conversions,3,Kotlin Programs,6,Lambda,1,lang,29,Leap Year,1,live updates,1,Logging,1,Mac OS,2,Math,1,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,1,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,21,String,58,String Programs,9,String Revese,1,Swing,1,System,1,Tags,1,Threads,10,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,2,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program to Find GCD of Two Numbers
Java Program to Find GCD of Two Numbers
A quick java practical guide and program to find GCD of Two Numbers GCD means Greatest Common Divisor.
https://1.bp.blogspot.com/-zAbsxZs-Mug/XjhZAGIHJuI/AAAAAAAACPw/7zV_WsAh9QwZTKjGl9AERM4aCNvy9loxQCLcBGAsYHQ/s640/Java%2BProgram%2Bto%2BFind%2BGCD%2Bof%2BTwo%2BNumbers.png
https://1.bp.blogspot.com/-zAbsxZs-Mug/XjhZAGIHJuI/AAAAAAAACPw/7zV_WsAh9QwZTKjGl9AERM4aCNvy9loxQCLcBGAsYHQ/s72-c/Java%2BProgram%2Bto%2BFind%2BGCD%2Bof%2BTwo%2BNumbers.png
JavaProgramTo.com
https://www.javaprogramto.com/2020/02/java-find-gcd.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2020/02/java-find-gcd.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content