Определить, можно ли заданное натуральное число n представить в виде суммы двух квадратов - C (СИ)

Формулировка задачи:

Определить, можно ли заданное натуральное число n представить в виде суммы двух квадратов натуральных чисел

Решение задачи: «Определить, можно ли заданное натуральное число n представить в виде суммы двух квадратов»

Листинг программы

for(int i=1;i*i<=n/2;i++)
{
  for(int j=i;j*j<=n/2;j++)
  {
    if(i*i+j*j==n)return true;
  }
}

Объяснение кода листинга программы

В данном коде определен цикл for с двумя вложенными циклами for. Первый цикл выполняется для всех натуральных чисел от 1 до корня из заданного числа n (потому что в данном случае ищется представление числа n в виде суммы двух квадратов, и это представление должно быть возможно конечным). Второй цикл, вложенный в первый, также выполняется для всех натуральных чисел от i до корня из n/2 (потому что искомый результат не может содержать два квадрата, один из которых больше половины искомого числа). Внутри второго цикла проверяется, является ли сумма квадратов i и j равной числу n. Если это так, то возвращается значение true, что означает, что число n может быть представлено в виде суммы двух квадратов. Если такого значения не найдено, то после выполнения всех вложенных циклов возвращается значение false, что означает, что число n не может быть представлено в виде суммы двух квадратов.