Задача
Найдите все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.
Входные данные
Одно натуральное число $n$ $( n \leqslant 10000)$.
Выходные данные
Выведите в одной строке в возрастающем порядке все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 5 | 5 |
| 2 | 10 | 5 10 |
| 3 | 13 | 5 10 13 |
| 4 | 20 | 5 10 13 17 20 |
| 5 | 30 | 5 10 13 17 20 25 26 29 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; public class Ideone{ static boolean check(int n) { for (int i = 1; i * i < n; i++) // перебор всех i { double j = Math.sqrt (n - i * i); if ((j == Math.floor(j)) && (j != i)) // проверка j целое или дробное { return true; // комбинация найдена - возвращаем true } } return false; // комбинация не найдена - возвращаем false } public static void main(String a[]) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // считываем число, до которого будем искать for (int k = 5; k <= n; k++) // проверка для каждого k if (check(k)) System.out.print(k + " "); in.close(); } } |
Решение
Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.
Ссылки
Условие задачи на e-olymp
Код программы на ideone