在Kotlin中检查一个数是否为质数

1. Introduction

A prime number is a number that has no divisors other than one and itself. Non-prime numbers are called composite. Moreover, 1 is considered neither prime nor composite. Additionally, negative numbers are also not considered prime.

This tutorial will look at various methods to check if a number is prime in Kotlin.

2. Using Iteration

We can use a for loop to check if the number has any divisors. Utilizing the property that one of the factors of a number must be less than or equal to its square root, we iterate only till the square root of the number. This way, we can improve the algorithm’s efficiency by reducing the number of iterations.

Let’s look at the implementation:

fun isPrimeUsingUsingIteration(num: Int): Boolean {
    if (num < 2) return false
    val sqrt = sqrt(num.toDouble()).toInt()
    for (i in 2..sqrt) {
        if (num % i == 0) {
            return false        }
    }
    return true
}

We utilize a range to generate potential factors till the square root of the input number. If the input is less than two, we return false directly, as it can’t be prime.

3. Using a Functional Programming Paradigm

We can leverage the functional programming feature provided by Kotlin to rewrite the iterative approach:

fun isPrimeUsingFunctionalProgram(num: Int): Boolean {
    if (num < 2) return false
    val sqrt = sqrt(num.toDouble()).toInt()
    return (2..sqrt).none { num % it == 0 }
}

In this approach, we utilize the none() method on the range to check if any of the elements are a factor. As soon as it finds a number within the specified range that is a factor of the input, this method immediately returns false. If there are no factors, then it returns true.

4. Using BigInteger

Previous methods to check the primality works fine for smaller numbers. As the input number becomes more extensive, the algorithm’s efficiency reduces. Fortunately, more efficient algorithms, such as the Miller-Rabin test, work better for large numbers. 

The BigInteger class in Java already implements the primality check using the Miller-Rabin algorithm. Let’s look at the implementation using BigInteger:

fun isPrimeBigInt(num: Int): Boolean {
    if (num < 2) return false
    return num.toBigInteger().isProbablePrime(100)
}

Here, we use the method isProbablePrime() on a BigInteger to check if the number is prime. It takes a certainty value used by the algorithm to determine the number of iterations required to verify. Additionally, it is essential to note that using a very high certainty value causes performance degradation.

5. Conclusion

This article looked at different ways to check if a number is prime. Apart from the custom check, we also looked at the more efficient implementation of the Java Standard Library.

As always, the sample code used in this article is available over on GitHub.