Table of Contents
I wrote Euclidean Algorithm in Kotlin.
Euclidean Algorithm
One way to calculate the greatest common measure of 2 natural numbers. It is written in Euclidean Elements.
Example
Let’s calculate the greatest common measure of 46 and 36 with Euclidean Algorithm.
\begin{eqnarray} 46 & = & 36 \times 1 + 10 \\ 36 & = & 10 \times 3 + 6 \\ 10 & = & 6 \times 1 + 4 \\ 6 & = & 4 \times 1 + 2 \\ 4 & = & 2 \times 2 \end{eqnarray}Thus, the greatest common measure is 2.
Environment
- Kotlin 1.0.0
Code
Euclidean Algorithm is basically for 2 numbers, but the code I wrote can handle more numbers.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.* open class MainKt { companion object Static { @JvmStatic fun main(args: Array<String> = arrayOf()) { println( MainKt().solve( args.toList<String>(). map { it.toLong() } as MutableList<Long>)) } } fun solve(numList: MutableList<Long>): Long { var newList = numList.distinct().sorted() as MutableList var r: Long = 0 while (newList.count() > 1) { r = newList[0] newList = newList. takeLast(newList.count() - 1).map { it % newList[0]} as MutableList newList.add(r) newList = newList.distinct().sorted(). filter { it != 0L } as MutableList<Long> } return r } } |
main function calls solve. solve does the calculation.
solve calculate and return the greatest common divisor of the given natural numbers. main prints it to standard out.
When there is no greatest common divisor (no common factors), solve returns 1.
Maybe there is more effective algorithm.
Usage
If you create jar, you can execute it as follows.
Example
|
1 2 |
java -jar Jar.jar 82 48 36 72 # => 2 |
Application
Since the greatest common divisor can be obtained, it is possible to simplify fractions.
For example, a class Fraction for fractions can be created as follows. In the initialization process, the denominator and numerator are divided by the greatest common divisor to make it an irreducible fraction. If the denominator (numerator) becomes 1, it becomes an integer.
|
1 2 3 4 5 6 7 8 9 |
data class Fraction( var denominator: Long, var numerator: Long) { init { var r = MainKt().solve( mutableListOf(denominator, numerator)) denominator /= r numerator /= r } } |
