HCF and LCM : BlueJ

Objective :

The class LCMandHCF finds out the Highest Common factor (H.C.F) AND Lowest Common Multiple(LCM) using a simple Recursive Technique. In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. The number 54 can be expressed as a product of two other integers in several different ways:
54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \,
Thus the divisors of 54 are:
1, 2, 3, 6, 9, 18, 27, 54. \,
Similarly the divisors of 24 are:
1, 2, 3, 4, 6, 8, 12, 24. \,
The numbers that these two lists share in common are the common divisors of 54 and 24:
1, 2, 3, 6. \,
The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:
\gcd(54,24) = 6. \,

Reducing fractions

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,
{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}.
The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called relatively prime, or coprime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.
The least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is a multiple of both a and b. 

What is the LCM of 4 and 6?
Multiples of 4 are:
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76 etc.

and the multiples of 6 are:
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...
Common multiples of 4 and 6 are simply the numbers that are in both lists:
12, 24, 36, 48, 60, 72, ....
So the least common multiple of 4 and 6 is the smallest one of those: 12

Applications

When adding, subtracting, or comparing vulgar fractions, it is useful to find the least common multiple of the denominators, often called the lowest common denominator, because each of the fractions can be expressed as a fraction with this denominator. For instance,
{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}
where the denominator 42 was used because it is the least common multiple of 21 and 6.
The following formula reduces the problem of computing the least common multiple to the problem of computing the greatest common divisor (GCD):
\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}.
This formula is also valid when exactly one of a and b is 0, since gcd(a, 0) = |a|.
There are fast algorithms for computing the GCD that do not require the numbers to be factored, such as the Euclidean algorithm. To return to the example above,
\operatorname{lcm}(21,6) ={21\cdot6\over\operatorname{gcd}(21,6)} ={21\cdot 6\over 3}= \frac{126}{3} = 42.
Because gcd(a, b) is a divisor of both a and b, it's more efficient to compute the LCM by dividing before multiplying:
\operatorname{lcm}(a,b)=\left({|a|\over\operatorname{gcd}(a,b)}\right)\cdot |b|=\left({|b|\over\operatorname{gcd}(a,b)}\right)\cdot |a|.
This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results (overflow in the a×b computation). Because gcd(a, b) is a divisor of both a and b, and thus the division will be guaranteed to yield an integer, so the intermediate result can be stored in an integer. Done this way, the previous example becomes:
\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42. 
BlueJ Program Screenshot :




Java Program Source Code :


/**
 * the class LCMandHCF finds out the Highest Common factor (H.C.F) AND Lowest Common Multiple(LCM) 
 * using a simple Recursive Technique.  
 * @author SHANTANU KHAN
 * @mail shantanukhan1995@gmail.com
 * @website 0code.blogspot.com 
 * Program Type : BlueJ Program - Java
 */
import java.io.*;
public class LCMandHCF
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static int num1=0,num2=0,hcf=0,lcm=0,result=0;
    
    private void input()throws Exception
    {
        System.out.print("Enter the First Number : ");
        num1=Integer.parseInt(br.readLine());
        System.out.print("Enter the First Number : ");
        num2=Integer.parseInt(br.readLine());
    }
    
    public int hcf(int numA,int numB)
    {
        if(numA%numB!=0)
            return hcf(numB,(numA%numB));
        else
            return numB;
    }
    
    public static void main(String args[])throws Exception
    {
        LCMandHCF obj=new LCMandHCF();
        obj.input();
        result=obj.hcf(num1,num2);
        System.out.println("Highest Common Factor : "+result);
        System.out.println("Lowest Common multiple : "+((num1*num2)/result));
    }
}

© Shantanu Khan 0code  ® LCM and HCF