Java-приложение, которое находит число, нам нужно умножить число n, чтобы найти идеальный квадрат

Question

Как найти наименьшее число x, которое при умножении на n (например, 104) находит идеальный квадрат для этого числа?

Пример:
ВХОД: 104
ВЫХОД:26

SO 104 * 26 = 2704, КОТОРАЯ ИДЕАЛЬНАЯ КВАДРАТНАЯ. SQRT (2704) = 52

Также имейте в виду, что максимальное число, которое мы можем ввести, равно 10 ^ 12, поэтому программа должна быть действительно эффективной и быстрой.

Я имеюпробовал:

public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  long i = sc.nextLong();
  sc.close();
  for (int j = 0; j<i; j++) {
      double n = Math.sqrt((double) i *j);
      String number = String.valueOf(n).substring(String.valueOf(n).indexOf(".")).substring(1);
      if(number.equals("0") && n != 0.0) {
          System.out.println("RESULT: " + j);
          break;
      }
   }
}

Но моя программа занимает столько времени для чисел выше 10 ^ 6 (10+ минут). Есть ли более быстрый способ сделать это?

Спасибо