Gcd Kt Test Algorithm
The Gcd Kt Test Algorithm, also known as the Greatest Common Divisor test, is an effective computational method used to determine the greatest common divisor (GCD) of two or more integers. The GCD is the largest positive integer that can divide the given numbers without leaving a remainder. This algorithm has various applications, including simplifying fractions, solving Diophantine equations, and finding the lowest common multiple (LCM) of multiple numbers. The Gcd Kt Test Algorithm is based on the Euclidean algorithm, which is a widely used technique to compute the GCD of two numbers efficiently and has been known since ancient times.
The Gcd Kt Test Algorithm begins by comparing the given numbers, and it iteratively applies the Euclidean algorithm to reduce the problem to a simpler form. The Euclidean algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by the difference between the larger and smaller numbers. The algorithm repeatedly subtracts the smaller number from the larger number until both numbers become equal, which is the GCD. Alternatively, a more efficient implementation of the algorithm uses the modulo operation, which computes the remainder when the larger number is divided by the smaller number. This process is repeated until the remainder becomes zero, and the GCD is the last non-zero remainder. The Gcd Kt Test Algorithm is known for its simplicity and efficiency, making it a popular choice for solving problems that involve finding the GCD of multiple numbers.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.math
import org.junit.Test
import org.junit.Assert.*
class GcdKtTest {
@Test
fun gcd() {
assertEquals(1, gcd(1, 1))
assertEquals(8, gcd(24, 16))
assertEquals(8, gcd(16, 24))
assertEquals(16, gcd(16, 16))
assertEquals(1, gcd(13, 29))
assertEquals(8, gcd(40, 16))
assertEquals(5, gcd(40, 15))
}
@Test
fun lcm() {
assertEquals(1, lcm(1, 1))
assertEquals(48, lcm(24, 16))
assertEquals(48, lcm(16, 24))
assertEquals(16, lcm(16, 16))
assertEquals(377, lcm(13, 29))
assertEquals(80, lcm(40, 16))
assertEquals(120, lcm(40, 15))
assertEquals(1000000, lcm(1000000, 1000000))
}
}
