Need a Java program to compute the greatest common divisor (GCD) of two integers

Question

Need a Java program to compute the greatest common divisor (GCD) of two integers. The GCD is the largest integer which evenly divides both numbers. For example, the GCD of 21 and 35 is 7. The program MUST ask the user how many pairs of numbers they would like to input. The program should then read the pairs of whole numbers (no 0s). Example of output would be....

(Number 1) (Number 2) (GCD)

HINT: The GCD can be computed with Euclid's division algorithm. Let the given numbers be A and B, A>=B. Euclid's division algorithm has the following steps;

1. Compute the remainder C of dividing A by B

2. If the remainder C is zero, B is the greatest common divisor.

3. If C is not zero, replace A with B and B with the remainder C. Go back to step (1)

I know something similar has been answered on here already, but those answers did not allow the user to input the number of pairs. Thank you for your help.

Explanation / Answer

import java.util.Scanner;

/**
* @author
*
*/
public class GCDEuclid {

   /** Function to calculate gcd **/
   public int gcd(int p, int q) {
       if (p % q == 0)
           return q;
       return gcd(q, p % q);
   }

   public static void main(String[] args) {
       // TODO Auto-generated method stub

       Scanner scanner = null;
       try {
           scanner = new Scanner(System.in);
           int n;
           System.out
                   .print("How many pairs of numbers you would like to input:");
           n = scanner.nextInt();
           int a, b;
           GCDEuclid euclid = new GCDEuclid();
           for (int i = 1; i <= n; i++) {

               System.out.print("Enter the A and B for " + (i) + " time:");
               a = scanner.nextInt();
               b = scanner.nextInt();
               int gcdVal = euclid.gcd(a, b);
               System.out.println("GCD :" + gcdVal);

           }

       } catch (Exception e) {
           // TODO: handle exception
       }
   }

}

OUTPUT:

How many pairs of numbers you would like to input:3
Enter the A and B for 1 time:21 35
GCD :7
Enter the A and B for 2 time:87 66
GCD :3
Enter the A and B for 3 time:9 54
GCD :9

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.