在Kotlin中计算最大公约数

1. Introduction

Calculating the Greatest Common Divisor (GCD) of two numbers is a fundamental operation in number theory and has various applications in computer science and mathematics.

In this tutorial, we’ll explore how to implement a GCD calculation algorithm in Kotlin.

2. Greatest Common Divisor

The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder. It is also referred to as the Highest Common Factor (HCF) or the Greatest Common Factor (GCF). The GCD of any two numbers is never negative or zero as the least positive integer common to any two numbers is always one.

Here’s the formula to calculate the GCD of two positive integers (a, b):

GCD (a,b) = ab/LCM(a,b)

The Least Common Multiple (LCM) of two or more numbers is simply the smallest multiple that is evenly divisible by all the given numbers. In this formula, we’ll first calculate the product of our integers a and b, determine their LCM, and finally, divide the product by the LCM.

3. Finding the GCD of Two Numbers

There are different algorithms to compute the GCD, and one of the commonly used methods is the Euclidean algorithm, which by definition computes the Greatest Common Divisor of two integers.

3.1. The Euclidean Algorithm

Let’s go over the definition of the Euclidean algorithm:

GCD(a, b) = GCD(b, a mod b)

Now, we’ll use this formula to calculate the GCD of two numbers, a = 48 and b = 18.

We compute the GCD of 48 and 18 by looking at the GCD of 18 and the remainder (12) of 48 divided by 18. Now, we can repeat this process to find the GCD of 18 and 12. Next up, we do the same thing again: express the GCD of 18 and 12 as the GCD of 12 and the remainder (6) of 18 divided by 12. Repeating this process, again we find that the GCD of 12 and 6 is the same as the GCD of 6 and the remainder (0) of 12 divided by 6.

We conclude the process because the remainder has now reached zero. The last non-zero remainder encountered in this series is 6, therefore the GCD of 48 and 18 is 6.

3.2. Implementation

Let’s see a code example of the Euclidean algorithm:

fun calculateGCD(a: Int, b: Int): Int {
    var num1 = a
    var num2 = b
    while (num2 != 0) {
        val temp = num2
        num2 = num1 % num2
        num1 = temp
    }
    return num1
}

In this code, our calculateGCD() function takes two integers, a and b, as parameters and uses a while() loop to continue the Euclidean Algorithm until num2 becomes zero. Each iteration calculates the remainder of the division num1 % num2 and updates num1 and num2 accordingly. The GCD is the last non-zero value of num1.

Note that it doesn’t matter which number is num1 or num2 initially. The algorithm works by iteratively updating num1 and num2 until num2 becomes zero. We swap the values on each iteration to ensure that num1 is always the larger number and num2 is the remainder.

Let’s verify our calculateGCD() function with a test:

@Test
fun `Should calculate GCD for two integers`() {
    assertEquals(6, calculateGCD(18, 48))
    assertEquals(1, calculateGCD(17, 5))
    assertEquals(9, calculateGCD(27, 18))
    assertEquals(15, calculateGCD(75, 45))
}

4. Finding the GCD of a List of Numbers

Next, we’re going to see how we can calculate the GCD of a list of numbers:

fun calculateGCDForListOfNumbers(numbers: List<Int>): Int {
    require(numbers.isNotEmpty()) { "List must not be empty" }
    var result = numbers[0]
    for (i in 1 until numbers.size) {
        var num1 = result
        var num2 = numbers[i]
        while (num2 != 0) {
            val temp = num2
            num2 = num1 % num2
            num1 = temp
        }
        result = num1
    }
    return result
}

Essentially, our calculateGCDForListOfNumbers() function uses the Euclidean algorithm to iteratively calculate the GCD of pairs of numbers in the input list, updating the result until the entire list is processed. Finally, the result is the GCD of all the numbers in the list.

At this point, let’s verify our calculateGCDForListOfNumbers() function with some tests:

@Test
fun `Should calculate GCD for list of two Intergers`() {
    val result = calculateGCDForListOfNumbers(listOf(21, 36))
    assertEquals(3, result)
}

@Test
fun `Should calculate GCD with three Intergers`() {
    val result = calculateGCDForListOfNumbers(listOf(10, 20, 30))
    assertEquals(10, result)
}

Let’s also confirm that our function throws an exception when the list is empty:

@Test
fun `Should fail on empty list`() {
    assertFailsWith<IllegalArgumentException> {
        calculateGCDForListOfNumbers(emptyList())
    }
}

To this end, our test proves that calculateGCDForListOfNumbers() can’t be called with an empty list. If that happens, an IllegalArgumentException is thrown, as expected, enforcing the requirement that the list must not be empty.

5. Conclusion

In this article, we’ve defined what the GCD is, and we’ve learned how we can calculate the GCD of two or more integers by leveraging an implementation of the Euclidean algorithm in Kotlin.

The full implementation of these examples is available over on GitHub.

Persistence

REST

Security