GCD Program Using Division Method in Java and Python
GCD program using successive division with algorithm, explanation, Java solution and simple Python solution for ICSE and ISC students.
Question:
Write a program to input 2 numbers and find their Greatest Common Divisor (GCD).
Note: If the 2 numbers are 54 and 24, then the divisors (factors) of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.
Similarly the divisors (factors) of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.
The numbers that these two lists share in common are the common divisors (factors) of 54 and 24: 1, 2, 3, 6.
The greatest (highest) of these is 6. That is the greatest common divisor or the highest common factor of 54 and 24.
Calculating HCF / GCD by Prime Factorisation Method is long and more time-consuming, and due to these disadvantages new method was evolved by Mathematician namely, Successive Division Method Under Successive Division Method, HCF / GCD = The Last Divisor of the given numbers . Following example can guide you How to calculate HCF / GCD by Successive Division Method ? Example : By using Successive Division Method, find the GCD of 24 & 18 ?
Answer : Steps and the way of finding GCD by Successive Division Method is as :-
Step 1 = Divide the larger number 24 by the smaller number 18. And this division will give remainder 6. Step 2 = Now, divide 18 (divisor of step 1) with 6 (remainder of step 1) Step 3 = Division in Step 2 give us remainder 0 (Zero). And The Last Divisor is the GCD of 24 & 18. Hence, GCD = 6
18 | 24 | 1
18
______
6 | 18 | 3
18
______
0Algorithm:
Step 1: Start.
Step 2: Accept two numbers a and b.
Step 3: If b is greater than a, swap the two values so division starts clearly.
Step 4: Repeat while b is not 0.
Step 5: Find remainder r = a % b.
Step 6: Store b in a because the old divisor becomes the new dividend.
Step 7: Store r in b because the old remainder becomes the new divisor.
Step 8: When b becomes 0, the current value of a is the GCD.
Step 9: Display a as the greatest common divisor.
Step 10: Stop.
Explanation:
The program uses Euclid’s division method to find the greatest common divisor of two numbers. The key mathematical idea is that the GCD of two numbers does not change if the larger number is replaced by the remainder obtained after division. For example, the GCD of 48 and 18 is the same as the GCD of 18 and 12, because 48 divided by 18 leaves remainder 12.
In the loop, r = n1 % n2 calculates the remainder. Then the old divisor n2 becomes the new dividend by assigning it to n1. The remainder becomes the new divisor by assigning it to n2. This shift is the heart of Euclid’s method. The program keeps repeating this process while n2 is not zero.
When the remainder finally becomes zero, it means the current divisor divides the previous number exactly. At that stage, the current value stored in n1 is the GCD. The program does not need to store all factors or test every number from 1 upward. It reduces the problem step by step using remainders, making it much faster and cleaner than the simple factor-counting method.
The loop is controlled by the divisor becoming zero, not by checking all possible factors. This is why the method remains short and reliable even for large inputs. Each remainder step keeps the common divisors unchanged while reducing the numbers.
Java Program:
/**
* The class Gcd inputs two numbers and finds their Gcd
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/
import java.util.*;
class Gcd
{
public static void main(String args[])throws Exception
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the First no : ");
int n1=sc.nextInt();
System.out.print("Enter the Second no : ");
int n2=sc.nextInt();
int r;
while(n2 != 0)
{
r = n1 % n2;
n1 = n2;
n2 = r;
}
System.out.print("GCD = "+n1);
}
}Alternate Java Program Using Subtraction Method:
/**
* The class Gcd inputs two numbers and finds their Gcd
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/
import java.util.*;
class Gcd
{
public static void main(String args[])throws Exception
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the First no : ");
int n1=sc.nextInt();
System.out.print("Enter the Second no : ");
int n2=sc.nextInt();
while(n1 != n2)
{
if(n1 > n2)
n1 = n1-n2;
else
n2 = n2-n1;
}
System.out.print("GCD = "+n1);
}
}Equivalent Python Program:
# Read the number and keep any required copy for digit or divisor processing.
# Loops and conditions implement the number-property test step by step.
# Display the result according to the flag/counter/calculated value.
n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))
while n2 != 0:
r = n1 % n2
n1 = n2
n2 = r
print("GCD =", n1)Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.