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 に答える