LearnFrenzy
Sign in Take a free test

Control Flow Statements · Control Flow Programs · Question 4

GCD and LCM using Euclid's algorithm in Java Solution, output & explanation

  • Program
  • Easy
  • 0 comments
  • Answer explained
  • Moderated community
Question 4 Back to Exercise

Read pairs of numbers and print their GCD (with a while loop implementing Euclid's algorithm) and LCM (computed without overflow).

Solution
Main.java
import java.util.Scanner;

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
        return Math.abs(a);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLong()) {
            long a = in.nextLong(), b = in.nextLong();
            long g = gcd(a, b);
            long lcm = g == 0 ? 0 : a / g * b;           // divide first to avoid overflow
            System.out.println("gcd(" + a + ", " + b + ") = " + g + ", lcm = " + lcm);
        }
    }
}

Output Verified by compiling and running

gcd(48, 18) = 6, lcm = 144
gcd(17, 5) = 1, lcm = 85
gcd(100000, 250000) = 50000, lcm = 500000
gcd(0, 9) = 9, lcm = 0

gcd(a, b) = gcd(b, a mod b) until the remainder is 0. a / g * b avoids computing the large product a * b first.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links