1

1からNまでのすべての数の約数を見つけるために、次を使用するとします。

for (i = 1; i < N; ++i) 
    for (j = i; j < N; j += i) 
        factors[j]++;

[a,b]範囲が次のようなものである場合はどうすればよいですか？1 < a,b < 10^9 and b-a < 10,000?
上記のコードを次のように適合させた場合：

for (i = 1; i < b; ++i)
    for (j = i; j < b; j += i)
        factors[j]++;

の場合、実行に時間がかかりすぎますb = 10^9。では、baがaとbに比べて小さく、aとbが大きい（10 ^ 9以上）とすると、どのような最適化を行うことができますか？

PS。多分私は問題をうまく説明できなかった。私が実際に見つける必要があるのは、範囲内の除数の数がいくつかに等しい数です。x <= 100.

ありがとう。

4

2 に答える 2

2

基本的な答えは、関心のある各数の因数分解を計算し、それを使用して除数の数を計算することです。因数分解がa ^ w * b ^ x * c ^ y * d ^ zの場合、除数の数は（ w + 1）*（x + 1）*（y + 1）*（z + 1）。

因数分解はいくつかの方法で見つけることができます。1つの方法は、試行割り算です。10 ^ 9の制限が小さいので、試行割り算はあまり苦労せずに機能します。もう1つの方法は、ふるいにかけ、エラトステネスのセグメント化されたふるいを使用して因子を見つけ、除算によってそれらの多重度を計算することです。

試行割り算、エラトステネスの分節化されたふるい、および数値の除数の計算のためのアルゴリズムとコードは、私のブログで見つけることができます。メニューバーの[演習]、[テーマ]、[素数]の順にクリックします。

編集：これが私がそれをする方法です。

最初のステップは、範囲内のすべての数値の要因をふるいにかけることです。エラトステネスのふるいを使用して、bの平方根よりも小さい素数を計算します。長さb - a +1の配列を作成し、各要素を空のリストに初期化します。bの平方根よりも小さい各素数について、素数の倍数であるa以上の最初の数kを計算し、次に、 k --aで始まり、 p --k -- a +の間隔で各配列要素について計算します。p、k - a + 2p、k - a + 3pなど-配列位置のリストにpを追加します。これにより、範囲内のすべての数値の因子のリストが得られますが、それらの多重度は得られません。

2番目のステップは、範囲内のすべての数値の除数の数を計算することです。配列の各要素iにはリストが含まれています。リストが空の場合、数は素数であり、数a + iには2つの除数があります。それ以外の場合は、リスト内の既知の因子による試行除算を使用してそれらの多重度を決定し、それらの多重度を使用して除数の数を計算します。

次に、 xに等しい除数の数を持つ範囲内のそれらを数えます。

于 2012-12-19T03:13:53.997 に答える
0

：1 <a <= n <= b <10 ^ 9などの任意の数nの場合、非常に単純なアルゴリズムでnの素因数分解が得られます（sqrt（n）より先に進む必要はありません）。それからあなたがそれを持っていると、式はあなたに異なる除数の数を与えるでしょう。

nの数はかなり少ないので、これでうまくいくはずです。

于 2012-12-19T03:03:47.663 に答える