Question

First write a method to calculate the greatest common divisor (GCD) of two positive integers using Euclid’s algorithm (also known as the Euclidean algorithm). Then write a main method that requests two positive integers from the user, validates the input, calls your method to compute the GCD, and outputs the return value of the method (all user input and output should be done in main). Check Wikipedia to find more information about GCDs1 and Euclid’s algorith

Answer 1

import java.util.Scanner;

public class Gcd

{

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.print("Enter two numbers to find their GCD: ");

int number1 = input.nextInt();

int number2 = input.nextInt();

if(number1 > 0 && number2 > 0)

System.out.println("GCD of " + number1 +" and " + number2 +" is: " + findGCD(number1, number2));

else

System.out.println("Invalid Input!");

}

public static int findGCD(int number1, int number2) {

if(number2 == 0){

return number1;

}

return findGCD(number2, number1 % number2);

}

}

Step-by-step explanation:

To be able to find GCD, we need to factorize the numbers and multiply common factors.

- Inside the function:

- Recursively divide number1 by number2 until number2 is equal to zero.

- Return number1 when the number2 is equal to zero. That means we found all the divisors of number1

- Inside the main:

- Ask user to input numbers

- Check if both numbers are greater than zero

- If they satisfy the condition, call the method and print the result.