Find GCD of Two number in Java - Euclidean algorithm - 2024

 Finding GCD of Two Number

    First we need to modules the first number by second number, then store the output in second number.

    Before doing the modules store the second number value for next iteration in temp variable. And do the process still the second number becomes zero.

Code :

package com.dinatechy.challange;

import java.util.Scanner;

public class GCDofNumber {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Enter the first number: ");

int num1 = scanner.nextInt();

System.out.print("Enter the second number: ");

int num2 = scanner.nextInt();

scanner.close();

// Calculate the GCD

int gcd = findGCD(num1, num2);

// Print the result

System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);

}

// Method to find the GCD using the Euclidean algorithm

public static int findGCD(int a, int b) {

// b = a % b, c = num2 % c,

while(b != 0) {

int temp = b;

System.out.println(a+" % "+b);

b = a % b;

a = temp;

System.out.println(b);

}

return a;

}

}

Input:

Enter the first number: 36

Enter the second number: 60

Output :

36 % 60

36

60 % 36

24

36 % 24

12

24 % 12

0

The GCD of 36 and 60 is: 12

Follow us for more useful Coding....