номер 2, страница 68, часть 1 - гдз по математике 5 класс учебник Алдамуратова, Байшоланова

2. Как найти пару делителей натурального числа?

Парой делителей натурального числа $\text{n}$ называется любая пара натуральных чисел $(d_1, d_2)$, произведение которых равно $\text{n}$. То есть, $d_1 \cdot d_2 = n$. Из этого следует, что если мы найдем один делитель $d_1$, то второй делитель $d_2$ можно легко вычислить как $d_2 = n / d_1$.

Общий алгоритм нахождения пары делителей

Чтобы найти пару делителей (кроме тривиальной пары $(1, n)$), можно использовать следующий эффективный метод:

1. Возьмем натуральное число $\text{n}$.

2. Начнем проверять целые числа $\text{d}$, начиная с $\text{2}$, на предмет того, являются ли они делителями $\text{n}$.

3. Проверку достаточно производить для $\text{d}$ в диапазоне от $\text{2}$ до $\lfloor\sqrt{n}\rfloor$ (целая часть от квадратного корня из $\text{n}$).

Почему до $\sqrt{n}$? Если у числа $\text{n}$ есть делитель $d > \sqrt{n}$, то парный ему делитель $k = n/d$ будет меньше, чем $\sqrt{n}$ (поскольку если бы оба делителя были больше $\sqrt{n}$, их произведение было бы больше $\text{n}$), и мы бы уже нашли этот меньший делитель $\text{k}$ на предыдущих шагах. Если $\text{n}$ — полный квадрат, то $\sqrt{n}$ будет его делителем, и пара будет $(\sqrt{n}, \sqrt{n})$.

4. Для каждого $\text{d}$ в указанном диапазоне проверяем, делится ли $\text{n}$ на $\text{d}$ без остатка. В математической записи это означает, что $n \pmod d = 0$.

5. Как только мы находим первое такое $\text{d}$, мы нашли делитель. Второй делитель в паре будет $k = n/d$. Таким образом, мы нашли пару делителей $(d, k)$. Если нужно найти только одну пару, на этом можно остановиться.

6. Если мы проверили все числа до $\lfloor\sqrt{n}\rfloor$ и не нашли ни одного делителя, это означает, что число $\text{n}$ является простым. Его единственная нетривиальная пара делителей — это $(1, n)$.

Пример: Найти пару делителей для числа 72

1. Дано число $n = 72$.

2. Найдем границу для поиска: $\sqrt{72} \approx 8.48$. Значит, нам нужно проверять делители от $\text{2}$ до $\text{8}$.

3. Начинаем перебор:

- Проверяем $d=2$: $72 \div 2 = 36$. Деление без остатка. Мы нашли делитель $\text{2}$.

- Находим второго делителя в паре: $k = 72 / 2 = 36$.

- Получаем пару делителей $(2, 36)$.

Поскольку задача — найти пару делителей, мы ее решили. Если бы нам нужно было найти все пары, мы бы продолжили проверку:

- $d=3$: $72 \div 3 = 24$. Пара $(3, 24)$.

- $d=4$: $72 \div 4 = 18$. Пара $(4, 18)$.

- $d=5$: $72$ не делится на $\text{5}$.

- $d=6$: $72 \div 6 = 12$. Пара $(6, 12)$.

- $d=7$: $72$ не делится на $\text{7}$.

- $d=8$: $72 \div 8 = 9$. Пара $(8, 9)$.

Проверка завершена, так как мы дошли до $\text{8}$. Все пары (кроме тривиальной $(1, 72)$) найдены.

Ответ: Чтобы найти пару делителей натурального числа $\text{n}$, нужно найти один его делитель $\text{d}$ (отличный от 1 и $\text{n}$), а затем вычислить второй делитель как $k = n/d$. Эффективный способ найти $\text{d}$ — это перебирать целые числа, начиная с 2, и проверять, делят ли они $\text{n}$ без остатка. Этот перебор достаточно вести до $\sqrt{n}$. Как только первый такой делитель $\text{d}$ найден, пара $(d, n/d)$ является искомой.