Scala Program to Find GCD of Two Numbers

Posted in

Sangeeta Gulia
Last updated on January 13, 2023

    GCD stands for Greatest Common Divisor. The GCD of two numbers is the largest common number that divides them completely. It is also called HCF, which stands for Highest Common Factor.

    Examples

    • For 16 and 20, 4 is the GCD.
    • The GCD for 11 and 121 is 11.

    After going through the definition, you may have gone back to the golden school days. You may have calculated the GCD of two numbers in your school time.

    The approach commonly used in school is something like the below one:

    Considering the first example,

    16 = 2 * 2 * 2 * 2

    20 = 2 * 2 * 5

    In both the above factors, 2*2 is common, leading to 4 as the highest common factor.

    Another way to do the same can be to write down the factors of a number and choose the highest factor that divides the two numbers.

    An example is given below:

    For 25 and 15,

    The factors of 25 are 25, 5, and 1, and that of 15 are 5, 3, and 1.

    The highest common factor (HCF) of the two numbers is 5.

    Now, you know how to find the GCD of two numbers. Let us now move on to writing the logic for your program and the actual program.

    Steps to Design Logic to Calculate the GCD of Two Numbers

    The following are some considerations you must know while writing a program to calculate the GCD:

    • From the above example, we can infer that HCF between the two numbers cannot exceed the minimum of the two numbers.
    • A number will be HCF only if it completely divides the two numbers.
    • To find a possible solution, we need to use a loop construct.
    • Since we have to compute the highest common factor, starting from the highest value in the loop will help to produce an optimized solution.

    Note : 1 is always the GCD of two numbers if no other possible numbers commonly divide the two input numbers.

    Let us give the above explanation a program look.

    Program

    import scala.collection.mutable.ListBuffer
    objectGCDextendsApp {
    
    val number1 = 15
    val number2 = 25
    
    defcalculatePrimeFactors(number: Int): ListBuffer[Int] = {
    val primeFactors = scala.collection.mutable.ListBuffer.empty[Int]
    for (i <- number to 1 by -1) {
    if(number % i == 0) {
    primeFactors.addOne(i)
    }
    }
    primeFactors
    }
    
    val primeFactorsNumber1: ListBuffer[Int] = calculatePrimeFactors(number1)
    val primeFactorsNumber2: ListBuffer[Int] = calculatePrimeFactors(number2)
    
    println(s"Prime factors for ${number1} is ${primeFactorsNumber1}")
    println(s"Prime factors for ${number2} is ${primeFactorsNumber2}")
    
    val commonFactors = primeFactorsNumber1.intersect(primeFactorsNumber2)
    println("Common prime factors are : " + commonFactors)
    
    println("The HCF of the two numbers is " + commonFactors.max )
    }
    

    Output

    Sample output 1:

    Prime factors for 15 is ListBuffer(15, 5, 3, 1)
    
    Prime factors for 25 is ListBuffer(25, 5, 1)
    
    Common prime factors are : ListBuffer(5, 1)
    
    The HCF of the two numbers is 5

    Sample Output 2:

    Prime factors for 30 is ListBuffer(30, 15, 10, 6, 5, 3, 2, 1)
    
    Prime factors for 18 is ListBuffer(18, 9, 6, 3, 2, 1)
    
    Common prime factors are : ListBuffer(6, 3, 2, 1)
    
    The HCF of the two numbers is 6

    Sample Output 3:

    Prime factors for 11 is ListBuffer(11, 1)
    
    Prime factors for 5 is ListBuffer(5, 1)
    
    Common prime factors are : ListBuffer(1)
    
    The HCF of the two numbers is 1

    Explanation

    In the above example, we used two variables, number1, and number2, to take user input. We wrote a method to calculate the factors of the input numbers.

    To calculate the common factors, we used the intersect method provided by the ListBuffer collection. It helps you find out the common numbers among the two lists.

    In the end, we calculated the highest element from the list of common factors using the max method on ListBuffer. The number you get is the GCD of two numbers.

    Conclusion

    We have provided one solution for calculating the GCD of a number. You can also try other approaches to calculate GCD, using other variations like Euclid's division algorithm and Long Division Method.

    Happy Coding!

    Leave a Comment on this Post

    0 Comments