algorithm - 如何除数形式为kn ^ p的筛子？

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
为所有数字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的除数

最佳答案

不用直接计算除数，可以使用这个公式（取自Wikipedia）：
这将有助于您在使用k内存时找到所有平方/立方/的除数，使其达到O(n)个数（nk）的幂。

// 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*nk，找到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，要找到的除数的数目。

关于algorithm - 如何除数形式为kn ^ p的筛子？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16227758/