perfect-square - java gui visual studio code - 整数の平方根が整数であるかどうかを判断する最も早い方法

javafx vscode / java / math / optimization

long 値が完全な平方であるかどうか(つまり、その平方根が別の整数であるかどうか)を判断するための最速の方法を探しています。

今、私がやっている非常にシンプルでわかりやすい方法をご紹介します。

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

18 revs, 13 users 36%



Answer #1

(非負の)整数で二分探索を実行して、 t**2 <= n なる最大の整数tを見つけます。次に、 r**2 = n かどうかを正確にテストします。これには時間O(log n)がかかります。