为何Kotlin中带step 2的for循环质数判断性能远逊于while循环？

我发现以下质数判断代码中，使用step 2的for循环（isPrime3）执行耗时（6528700纳秒）远高于普通for循环（isPrime2，182800纳秒）和手动步长的while循环（isPrime4，11401纳秒）。请问这是什么原因？还是我的实现存在问题？

测试代码 #

println(measureNanoTime {
    println(isPrime2(999999999)) // O(n) ==> time is 182800 
})

println(measureNanoTime {
    println(isPrime3(999999999)) // O(n/2) using step 2 ==> time is 6528700
})

println(measureNanoTime {
    println(isPrime4(999999999)) // O(n/2) using while loop ==> time is 11401
})

fun isPrime2(n: Int): Boolean {
    if (n == 2) return true
    if (n < 2 || n % 2 == 0) return false

    for (i in 3 until n) {
        if (n % i == 0) return false
    }
    return true
}

fun isPrime3(n: Int): Boolean {
    if (n == 2) return true
    if (n < 2 || n % 2 == 0) return false

    for (i in 3 until n step 2) {
        if (n % i == 0) return false
    }
    return true
}

fun isPrime4(n: Int): Boolean {
    if (n == 2) return true
    if (n < 2 || n % 2 == 0) return false

    var i = 3
    while (i < n) {
        if (n % i == 0) return false
        i += 2
    }
    return true
}

原因分析 #

1. 测试用例的特殊性 #

你测试的999999999是合数，第一个能整除它的奇数就是3，三个函数的循环都只执行1次就直接返回false。这种场景下，循环执行的开销可以忽略，真正影响耗时的是循环结构的初始化成本：

• isPrime2的普通for循环：编译后生成接近while的字节码，初始化开销小。
• isPrime3的step 2for循环：Kotlin会基于IntProgression创建迭代器，迭代器的创建、初始化带来额外开销，在循环仅执行1次时，这个开销会被放大，导致总耗时飙升。
• isPrime4的while循环：完全手动控制变量递增，无额外迭代器或框架开销，初始化成本最低，所以耗时最短。

2. JVM预热与测量误差 #

你的测试顺序是isPrime2→isPrime3→isPrime4，JVM的即时编译器（JIT）会在函数多次调用后优化代码。isPrime4可能享受到了前面函数调用带来的JVM预热，而isPrime3作为第二个被调用的函数，可能刚好遇到JIT编译的中间状态，导致测量结果出现偏差。多次重复测试或调整测试顺序，耗时差异会明显缩小。

3. 实现上的性能缺陷 #

三个函数都存在严重性能问题：循环上限设为n完全没必要。质数判断的数学原理是：如果n有因数，必然存在一个不大于sqrt(n)的因数。循环只需遍历到sqrt(n)即可，这会把循环次数从接近10亿直接降到3万左右，整体性能提升几个数量级。

优化后的代码 #

fun isPrimeOptimized(n: Int): Boolean {
    if (n == 2) return true
    if (n < 2 || n % 2 == 0) return false

    val sqrtN = kotlin.math.sqrt(n.toDouble()).toInt()
    var i = 3
    while (i <= sqrtN) {
        if (n % i == 0) return false
        i += 2
    }
    return true
}

这个版本保留了while循环的低开销，又通过缩小循环上限极大提升了性能，不管是质数还是合数，执行效率都远高于原来的三个函数。

内容的提问来源于stack exchange，提问作者3bdoelnaggar