1

したがって、素因数分解と除数取得のためのアルゴリズム (ネットで簡単に検索可能) がありますが、範囲内でそれらの除数を見つけるためにそれをスケーリングする方法がわかりません。たとえば、23 から 49 (任意) までの 100 のすべての約数。しかし、効率的なものでもあるので、これをより大きな範囲で大きな数にスケーリングできます。最初は、範囲のサイズである配列を使用してから、すべての素数 <= 上限を使用して、その配列内のすべての要素をふるいにかけて、除数の最終的なリストを返すことを考えていましたが、大きな範囲の場合、これもそうですメモリ集約的。

除数を直接生成する簡単な方法はありますか?

4

3 に答える 3

2

あなたn[i]の数のi番目の要素をx<iとしmます。j1より大きく、より小さい整数の場合、のビットがで2^mあるすべての積は、の約数です。n[j[r]]j[r]r-thjx

105を考えてみましょう。その要因は[3, 5, 7]です。したがって、3ファクター、2 ^ 3は8です：

 0  000                = 1
 1  001              7 = 7
 2  010          5     = 5
 3  011          5 * 7 = 35
 4  100      3         = 3
 5  101      3   *   7 = 21
 6  110      3 * 5     = 15
 7  111      3 * 5 * 7 = 105

見る？105のすべての可能な除数（0と7は少し疑わしいです）。

于 2013-03-11T00:13:14.107 に答える
0

Malvolio が (間接的に) 行っていたように、範囲内の因数を見つけたい場合、個人的に素因数分解の使用法を見つけることはできませんでした。int t = (int)(sqrt(n)) から始めて、
1. t は係数です
2. 完全な util t または t/n 範囲に達し (フラグ)、その後 (両方とも) 範囲を超えました

または、範囲が比較的小さい場合は、それらの値自体と比較して確認してください。

于 2013-03-11T00:54:54.130 に答える
-1

n の約数がわかっている場合は、nの約数を計算できます--- 1 とnを含む、n を均等に分割する数値 --- nの約数のベキ集合の積をとることによって計算できます。

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

除数の完全なリストを取得したら、必要な範囲にあるものだけを選択できます。

于 2013-03-11T03:15:59.623 に答える