2

为所有数字 1-n 创建一个除数计数筛是众所周知的

func sieve(n)
    counts = array of size n+1, all elements set to 1, counts[0] = 0 arbitrary

    for 2 <= i <= n
        for i <= j <= n, stepwise i
            counts[j]++;
    return counts

但是，如果我不是为形式 1 * n 的数字创建筛子，而是希望为形式为 6n^2 的数字创建除数，该怎么办？

因此，与其查找 1、2、3、4、5 等的除数，不如查找 6、24、54、96、150 等的除数

但实际上只是形式 kn^p 的数字，以一种有效的方式，所以我实际上并没有存储一个大小为 kn^p 的最大数组。好像我应该只需要大小为 N 的数组，只有每个点代表 kn^p 的除数

4

1 回答 1

3

您可以使用以下公式（取自Wikipedia），而不是直接计算除数：

这将帮助您在使用内存时找到所有平方/立方体/k数字的幂 (n k ) 的除数。O(n)

// Stores the number of divisors for n^k
count[n + 1]

// Count number of divisors for 1^k, 2^k, ..., n^k
function countDivisors(n, k) {
    // Note: You can actually merge sieve function with the loop below
    prime[] = sieve(n)

    count[0] = 0
    count[1..n] = 1 // Set count[i] to count[n] to 1

    for all primes p <= n {
        for (i = 1; p^i <= n; i++) {
            // You can cache the value of p^i for next loop
            pi = p^i 

            for (m = pi; m <= n; m += pi) {
                // We "replace" the previous count with current count
                count[m] = count[m] / ((i - 1) * k + 1) * (i * k + 1)
            }
        }
    }
}

要将其扩展到 a*n k，请找到 a 的素数分解，并记录素数以及相应的幂。

  • 如果任何素数大于n，您可以将它们带走并根据除数函数将它们减少为乘数。

  • 如果任何素数小于 n，将其提供给countDivisors上面的函数，并稍微修改函数：

    for all primes p <= n {
    // Note: You are free to optimize this in actual code
    let e be maximal power of p in a

    if (e > 0) {
        // Update all number with the factors from a
        for (i = 1; i <= n; i++) {
            count[i] *= (e + 1)
        }
    }

    for (i = 1; p^i <= n; i++) {
        // You can cache the value of p^i for next loop
        pi = p^i 

        for (m = pi; m <= n; m += pi) {
            // We "replace" the previous count with current count
            count[m] = count[m] / ((i - 1) * k + e + 1) * (i * k + e + 1)
        }
    }
}

如您所见，时间和空间复杂度不取决于幂k，而仅取决于n您想要找到其除数的数字的数量。

于 2013-04-26T04:12:13.433 回答