Задача Codewar. Как найти простые квадратные числа по условию?

Question

Я пытался решить эту проблему на Codewar, но не понимаю, как находить исключения.

В этом Кате вам будет присвоено число n (n> 0 ), и ваша задача будет заключаться в том, чтобы вернуть наименьшее квадратное число N (N> 0) такое, что n + N также является полным квадратом. Если ответа нет, верните -1 (ноль в Clojure, ничего в Haskell).

Вот код, который я написал:

using System;

public class SqNum
{
    public static long solve(long n){  
       int N = 1;
            long lTemp = n;
            double sum, result;
            bool isSqare;
            while(true)
            {
                sum = lTemp + N;
                result = Math.Sqrt(sum);
                isSqare = result % 1 == 0;
                if(n == 4)
                {
                  return -1;
                }

                if(isSqare == true)
                {
                    return Convert.ToInt32(result);
                }
                N++;
            }
            return -1;
      }
}

Answer 1

Если N (квадрат) равно p^2, а n+N=r^2, вы можете написать

n + p^2 = r^2
n = r^2 - p^2
n = (r - p) * (r + p)

Если мы представим n как произведение пары делителей:

n = a * b     // let a<=b
a * b = (r - p) * (r + p)

У нас есть система

r - p = a
r + p = b

и

p = (b - a) / 2

Когда p самый маленький? В случае максимально близких факторов b и a. Итак, мы можем попытаться вычислить делители, начиная с квадрата root из n. Также обратите внимание, что a и b должны иметь одинаковую четность (чтобы сделать p целое число)

Псевдокод:

int N = -1;
for (int a = Math.Ceiling(Math.Sqrt(n)) - 1; a > 0; a--) {
   if (n % a == 0) {
      int bma = n / a - a;
      if (bma % 2 == 0) {
         int p = bma / 2;
         int N = p * p;
         break;
      }
   }
}

Примеры:

n = 16
first divisor below sqrt(16) a = 2, b=8
p = 3, 16 + 9 = 25

n = 13
first divisor below sqrt(13) a = 1, b=13
p = 6, 13 + 36 = 49

n = 72
first divisor below sqrt(72) is a = 8, b= 9 - but distinct parity!
so the next suitable pair is a = 6, b = 12
p = 3, 72 + 9 = 81