2つの数字の間の平方根の数を見つけよう

Question

私は2つの数字の間の平方根の数を見つけるためにこの関数を書いています。

static int FindRoot(int no1, int no2) { 
    int res = 0; 
    for (int x = no1; x <= no2; x++) { 
     for (int y = 1; y <= no2; y++) { 
      if (y * y == x) 
       res++; 
     } 
    } 
    return res; 
} 

これは問題なく動作しますが、パフォーマンスについては考えていました。 この場合、inner For loopは開始位置（1）から実行されるため、誰かがメソッドに大きな数値範囲を渡すと時間がかかります。

だから、私の質問は：

私はより良いパフォーマンスでこれを見つけることができる他の方法はありますか？私が使用することはできません

PS- Math.sqrt()機能

Answer 1

static int FindRoot(int no1, int no2) { 
    int res = 0; 
    int x = 0; 

    // Ignore squares less than no1 
    while(x*x < no1) { 
     x++; 
    } 

    // Count squares up to and including no2 
    while(x*x <= no2) { 
     res++; 
     x++; 
    } 

    return res; 
} 

Answer 2

あなたが効果的に自分の内面を行う外側のループここ

static int findRoot(int lo, int hi) { 
    int numRoots = 0; 

    for (int x = 0, x2 = 0; x2 <= hi; x++, x2 = x * x) { 
     if (x2 >= lo) { 
      numRoots++; 
     } 
    }  

    return numRoots; 
} 

を取り除くことにより、ループのための単一を持つ逃げることができますx2（x-squared）がloとhiの間にあるときにnumRootsをインクリメントし、x2がhiより大きいときにループを終了する（xではなく）。あなたのコードのようなhiより大きい）。

Answer 3

これも機能します。

static int FindRoot2(int no1, int no2) { 
    int res = 0; 
    int inner=1; 
    for (int x = no1; x <= no2; x++) { 
     for (int y = inner; y <= no2; y++) { 
      if (y * y == x) 
      { 
       inner=y; 
       res++; 
      } 
     } 
    } 
    return res; 
} 

この場合、内側のループは、現在のアルゴリズムがineffecientですが、最大のものは、forループの内側には必要がないことである多くの理由がありますが1

Answer 4

から実行を開始しません。

あなたが探しているアルゴリズムの背後にあるアイデアは、no1以上の完全な正方形で始まり、次の完全な正方形と次の正方形に進み、あなたがいる完璧な広場がno2よりも高くなるまで、ヒットします。

static int FindRoot(int no1, int no2) { 

    int res = 0; 
    int x = 1; 

    // This loop gets x to the first perfect square greater than 
    // or equal to no1 
    while((x * x) < no1) { 
     x++; 
    } 

    // This loop adds 1 to res and increases x 
    // as long as x^2 is less than or equal to no2 
    for(; (x * x) <= no2; x++, res++) { } 

    return res; 
}