除数を直接数えるのではなく、次の式を使用できます ( 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