在Kotlin中检查数字是否为质数

Kahen大约 4 分钟

在Kotlin中检查数字是否为质数

质数是一个除了1和它自身外没有其他除数的数字。非质数称为合数。此外，1既不被视为质数也不被视为合数。还有，负数也不被视为质数。

本教程将探讨在Kotlin中检查数字是否为质数的多种方法。

2. 使用迭代

我们可以使用for循环来检查数字是否有任何除数。**利用一个数字的因子之一必须小于或等于它的平方根这一属性，我们只迭代到数字的平方根。**这样，我们可以通过减少迭代次数来提高算法的效率。

让我们看看实现：

fun isPrimeUsingIteration(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
}

我们使用一个范围来生成输入数字平方根之前的潜在因子。如果输入小于2，我们直接返回false，因为它不能是质数。

3. 使用函数式编程范式

我们可以利用Kotlin提供的函数式编程特性来重写迭代方法：

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

在这种方法中，我们利用范围上的_none()_方法来检查是否有任何元素是输入数字的因子。一旦它发现指定范围内有一个数字是输入的因子，这个方法会立即返回false。如果没有因子，则返回true。

4. 使用BigInteger

先前检查质数的方法对于较小的数字工作得很好。随着输入数字的增大，算法的效率降低。幸运的是，像Miller-Rabin测试这样的更有效算法更适合大数字。

Java中的_BigInteger_类已经实现了使用Miller-Rabin算法的质数检查。让我们看看使用_BigInteger_的实现：

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

在这里，我们使用_BigInteger_上的_isProbablePrime()_方法来检查数字是否为质数。它接受一个确定性值，该值由算法用来确定所需的迭代次数。另外，需要注意的是，使用非常高的确定性值会导致性能下降。

5. 结论

本文探讨了检查数字是否为质数的不同方法。除了自定义检查外，我们还看了Java标准库中更有效的实现方式。

和往常一样，本文中使用的示例代码可以在GitHub上找到。--- date: 2022-11-01 category:

Kotlin
Programming tag:
prime number
algorithm
BigInteger head:
- meta
- name: keywords content: Kotlin, prime number check, algorithm, BigInteger, programming

在Kotlin中检查数字是否为质数

质数是一个除了1和它自身外没有其他除数的数字。非质数称为合数。此外，1既不被视为质数也不被视为合数。还有，负数也不被视为质数。

本教程将探讨在Kotlin中检查数字是否为质数的多种方法。

2. 使用迭代

让我们看看实现：

fun isPrimeUsingIteration(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
}

我们使用一个范围来生成输入数字平方根之前的潜在因子。如果输入小于2，我们直接返回false，因为它不能是质数。

3. 使用函数式编程范式

我们可以利用Kotlin提供的函数式编程特性来重写迭代方法：

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

在这种方法中，我们利用范围上的none()方法来检查是否有任何元素是输入数字的因子。一旦它发现指定范围内有一个数字是输入的因子，这个方法会立即返回false。如果没有因子，则返回true。

4. 使用BigInteger

Java中的BigInteger类已经实现了使用Miller-Rabin算法的质数检查。让我们看看使用BigInteger的实现：

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

在这里，我们使用BigInteger上的isProbablePrime()方法来检查数字是否为质数。它接受一个确定性值，该值由算法用来确定所需的迭代次数。另外，需要注意的是，使用非常高的确定性值会导致性能下降。

5. 结论

本文探讨了检查数字是否为质数的不同方法。除了自定义检查外，我们还看了Java标准库中更有效的实现方式。

和往常一样，本文中使用的示例代码可以在GitHub上找到。