2

数か月前、StackOverflow で「線形時間で素数の因数を見つけるアルゴリズム」について質問しました。

返信で、私の仮定が間違っていて、アルゴリズムが線形時間で要因を見つけることができないことは明らかでした。

ただし、アルゴリズムが除算を行って因数を見つけるための独自の方法であるかどうかを知りたいです。つまり、除算を行うための同様の/同じ方法が知られていますか? 私は再びここにアルゴリズムを投稿しています：

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is found
  End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
  mL = mL-1;
  r = r+ mR;

  temp1 = r/mL;
  mR = mR + temp1;
  r = r%mL;
}
End; //mR and mL has answer

入力を教えてください/質問は、除算を行って因数を見つけるための同様のアルゴリズムが存在するかどうかを知るための純粋な個人的な関心からのものですが、私は見つけることができません.

答えを出すために私の面白いアルゴリズムを理解する必要があるかもしれないことを理解し、感謝します! :)

詳細な説明: はい、10 を超える数値 (テスト済み) とすべての正の整数で機能します。アルゴリズムは、さらに進むために剰余 r に依存します。私は基本的に、数値の約数は、面積が数値そのものである長方形の辺を与えるという考えを形成しました。約数ではない他のすべての数については、剰余が残るか、結果として長方形を完全に形成することができません。したがって、アイデアは、mL が減少するたびに、r = mR+r を増やすことができます (基本的に mR から 1 mR をシフトします)。mL を r に) し、この大きな r を mL で割って、mR をどれだけ増やすことができるか (mL を 1 回減らすために mR を何回増やすことができるか) を調べます。したがって、残りの r は r mod mL です。因数を見つけるために必要な while ループの数を計算しましたが、すべての数値で 5*N 以下になります。トライアル部門はそれ以上かかります。

お時間をいただきありがとうございます、ハリッシュ

4

2 に答える 2

2

メインループは、次のCコードと同等です。

mR = mL = sqrt(N);
...
mR = N/mL; // have the value of mL less than mR
r = N%mL;
while (r) {
  mL = mL-1;
  r += mR;
  mR = mR + r/mL;
  r = r%mL;
}

r += mR各ステートメントの後、rの値は。であることに注意してくださいr%(mL-1)+mR。なので、次のステートメントr%(mL-1) < mLのの値はまたはのいずれかです。私は（数値テストの結果として）ループから抜け出したときにそれがうまくいくことに同意しますが、その理由はわかりません。理由がわかっている場合は、方法を真剣に受け止めたいのであれば、その理由を説明する必要があります。r/mLmR/mL1 + mR/mLmR*mL = N

効率の点では、フェルマーの素因数分解と同じ数のループを使用しますが、フェルマーの素因数分解の内部ループは除算を使用せずに記述できます。この場合、メソッドは内部ループ内で2つの除算演算（r/mLおよび）を使用します。r%mL両方の方法の最悪の場合、内部ループは約sqrt（N）回実行されます。

于 2011-09-16T15:32:46.887 に答える
1

他にも、前の質問で既に説明したポラードの rho アルゴリズムや GNFS などがあります。

于 2011-09-16T07:41:38.683 に答える