如何更快获取区间内所有可整除数对？

我编写了一个Kotlin函数，用于计算给定区间[start, end]内的所有可整除数对，希望找到优化其性能的方法。

初始实现代码 #

fun getDivisiblePairsInRange(
    start: Int,
    end: Int,
    ignoreSelfDivision: Boolean = false,
): List<IntArray>
{
    if (start == 0) throw IllegalArgumentException("start parameter can't be 0")

    val oneOrZero = if (ignoreSelfDivision) 1.0 else 0.0

    val divisiblePairs = mutableListOf<IntArray>()

    for (numerator in start..end)
    {
        val optimizedEnd = ceil(sqrt(numerator - oneOrZero)).toInt()

        var divisorFromPreviousIteration = -1

        for (denominator in start..optimizedEnd)
        {
            if (numerator % denominator != 0 || denominator == divisorFromPreviousIteration) continue

            divisiblePairs += intArrayOf(numerator, denominator)

            val secondDivisor = numerator / denominator

            if (!(ignoreSelfDivision && numerator == secondDivisor) && denominator != secondDivisor) divisiblePairs += intArrayOf(numerator, secondDivisor)

            divisorFromPreviousIteration = secondDivisor
        }
    }

    return divisiblePairs
}

该函数的时间复杂度为O(n^1.5)，其中ignoreSelfDivision参数用于避免(a,a)这类数对，但这并非优化重点。

函数行为示例 #

以下是几个输入对应的输出，便于理解函数行为：

(1, 3)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3]]
(1, 5)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5]]
(1, 8)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5], [6, 1], [6, 6], [6, 2], [6, 3], [7, 1], [7, 7], [8, 1], [8, 8], [8, 2], [8, 4]]
(1, 10) -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5], [6, 1], [6, 6], [6, 2], [6, 3], [7, 1], [7, 7], [8, 1], [8, 8], [8, 2], [8, 4], [9, 1], [9, 9], [9, 3], [10, 1], [10, 10], [10, 2], [10, 5]]

优化版本（适配Kotlin的@Dave方案） #

fun getDivisiblePairsInRangeFromDave(
    start: Int,
    end: Int,
    ignoreSelfDivision: Boolean = false,
): List<IntArray>
{
    var ratio = end / start
    var currentDenominator = start
    val divisiblePairs = mutableListOf<IntArray>()

    while (ratio >= 1)
    {
        for (multiple in 1..ratio)
        {
            val numerator = currentDenominator * multiple

            if (ignoreSelfDivision && currentDenominator == numerator) continue

            divisiblePairs += intArrayOf(numerator, currentDenominator)
        }

        ratio = end / ++currentDenominator
    }

    return divisiblePairs
}

额外性能提升技巧 #

如果不需要返回具体数对，仅统计数对数量，可先实现统计逻辑，再用数组替代可变列表存储数对，性能可提升约30%。

内容的提问来源于stack exchange，提问作者Elián