Як знайти дільник числа: методи, алгоритми та приклади
Дільник числа — це натуральне число, на яке дане число ділиться без остачі. Уміння швидко і точно знаходити всі дільники потрібне не лише школярам, а й тим, хто працює з алгоритмами, криптографією чи просто розв’язує практичні задачі на поділ ресурсів.
У цій статті зібрано перевірені способи пошуку дільників: від елементарного перебору до розкладу на прості множники. Кожен метод пояснено з прикладами, нюансами та типовими помилками, щоб ви могли обирати оптимальний підхід залежно від розміру числа.
Матеріал охоплює як базові шкільні випадки, так і більш ефективні техніки, які використовують у програмуванні. Після прочитання ви зможете не лише знаходити дільники вручну, а й розуміти, чому той чи інший алгоритм працює саме так.
Що таке дільник і чому вміння його шукати важливе
За визначенням, натуральне число d є дільником числа n, якщо існує таке натуральне число k, що n = d × k. Інакше кажучи, при діленні n на d остача дорівнює нулю. Кожне натуральне число має щонайменше два дільники: 1 і саме себе. Числа, у яких рівно два дільники, називають простими. Усі інші (крім одиниці) — складені.
Пошук дільників лежить в основі багатьох математичних операцій. Без нього неможливо скоротити дроби, знайти найбільший спільний дільник (НСД), найменше спільне кратне (НСК) чи розкласти число на прості множники. У програмуванні алгоритми пошуку дільників використовують для перевірки простоти чисел, факторизації та оптимізації циклів.
З практики шкільних уроків і задач олімпіадного рівня видно: учні, які розуміють структуру дільників, значно швидше справляються з темами подільності та арифметичних прогресій. Той самий принцип працює і в дорослих задачах — від розподілу бюджету до аналізу періодичності явищ.
Базовий метод перебору: коли він достатній
Найпростіший спосіб — перевірити всі числа від 1 до n і відібрати ті, на які n ділиться без остачі. Алгоритм виглядає так:
- Беремо число n.
- Для кожного i від 1 до n перевіряємо, чи n % i == 0.
- Якщо так — додаємо i до списку дільників.
Для числа 36 перебір дає: 1, 2, 3, 4, 6, 9, 12, 18, 36. Метод працює завжди, але його складність O(n). Для чисел до кількох сотень це прийнятно, для тисяч і більше — вже повільно, особливо якщо робити вручну.
Перебір зручний для початківців, бо не вимагає додаткових знань. Він також допомагає зрозуміти саму ідею дільника: кожна пара чисел, добуток яких дорівнює n, автоматично дає два дільники.
Метод пар через квадратний корінь — основний практичний інструмент
Дільники завжди йдуть парами. Якщо d ділить n, то й n/d теж ділить. Більше того, один із дільників пари обов’язково не перевищує √n. Тому достатньо перевіряти числа лише до квадратного кореня.
Алгоритм:
- Обчислюємо √n (достатньо цілої частини).
- Перевіряємо всі i від 1 до √n.
- Якщо n ділиться на i, додаємо і i, і n/i (якщо вони різні).
- Наприкінці сортуємо список.
Візьмемо 48. √48 ≈ 6,9. Перевіряємо до 6:
- 1 → 48
- 2 → 24
- 3 → 16
- 4 → 12
- 6 → 8
Отримуємо повний набір: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Замість 48 перевірок зробили лише 6. Для чисел порядку 10 економія часу колосальна.
Важливий нюанс: коли n — повний квадрат, один дільник (сам корінь) додається лише один раз. Наприклад, для 36 корінь 6, і 6 з’являється в списку одноразово.
Як не пропустити жодного дільника
Під час роботи вручну зручно записувати пари стовпчиком:
| Менший дільник | Більший дільник |
|---|---|
| 1 | 48 |
| 2 | 24 |
| 3 | 16 |
| 4 | 12 |
| 6 | 8 |
Джерело: власні розрахунки на основі стандартного алгоритму.
Такий запис майже виключає пропуски. Якщо на якомусь кроці i вже більше за √n, зупиняємося.
Розклад на прості множники — спосіб отримати всі дільники одразу
Найпотужніший метод для великих чисел і для підрахунку кількості дільників. Спочатку розкладаємо n на прості множники, а потім комбінуємо їх усіма можливими способами.
Приклад для 60:
60 = 2² × 3¹ × 5¹
Будь-який дільник має вигляд 2 × 3 × 5, де 0 ≤ a ≤ 2, 0 ≤ b ≤ 1, 0 ≤ c ≤ 1. Перебираючи всі комбінації, отримуємо:
- 2⁰3⁰5⁰ = 1
- 2¹3⁰5⁰ = 2
- 2²3⁰5⁰ = 4
- 2⁰3¹5⁰ = 3
- 2¹3¹5⁰ = 6
- 2²3¹5⁰ = 12
- 2⁰3⁰5¹ = 5
- 2¹3⁰5¹ = 10
- 2²3⁰5¹ = 20
- 2⁰3¹5¹ = 15
- 2¹3¹5¹ = 30
- 2²3¹5¹ = 60
Усього 12 дільників. Цей підхід особливо зручний, коли потрібно не лише список, а й розуміння структури числа.
Для розкладу використовують метод послідовного ділення на прості числа (2, 3, 5, 7…) або більш просунуті алгоритми на кшталт Полларда, але для чисел до 10 достатньо звичайного перебору простих до √n.
Як порахувати кількість дільників без повного списку
Якщо розклад на прості множники відомий, кількість дільників обчислюється за простою формулою. Нехай n = p₁ × p₂ × … × pk. Тоді кількість додатних дільників дорівнює (a₁ + 1)(a₂ + 1)…(ak + 1).
Для 60 = 2² × 3¹ × 5¹ маємо (2+1)(1+1)(1+1) = 3 × 2 × 2 = 12. Для 720 = 2⁴ × 3² × 5¹ отримуємо (4+1)(2+1)(1+1) = 5 × 3 × 2 = 30 дільників.
Формула працює миттєво і не вимагає генерації самого списку. Її часто застосовують у задачах, де потрібно лише знати, скільки дільників має число, а не які саме.
Поширені помилки при пошуку дільників
Перша і найчастіша — забути, що 1 і саме число завжди є дільниками. Друга — перевіряти числа після √n і дублювати пари. Третя — плутати дільники з кратними. Кратне — це число, яке ділиться на дане, а дільник — навпаки.
Ще одна типова помилка виникає при роботі з квадратами: учні іноді додають корінь двічі або, навпаки, пропускають його. Також трапляється, що при розкладі на множники забувають про степені й отримують неповний список.
У програмуванні поширена помилка — використання циклу до n замість √n. На великих числах це призводить до відчутного уповільнення. Ще одна — неправильна обробка випадку, коли i × i == n.
З досвіду роботи з учнями видно: більшість помилок зникає, якщо завжди записувати пари й перевіряти результат множенням. Якщо добуток пари не дорівнює початковому числу — десь сталася помилка.
Практичні сценарії: школа, побут і код
У школі найчастіше потрібно знайти всі дільники, щоб визначити, просте число чи складене, або щоб скоротити дріб. Наприклад, щоб скоротити 48/60, знаходимо спільні дільники і ділимо чисельник і знаменник на найбільший з них (12).
У побуті задача виникає при розподілі предметів на рівні групи. Якщо у вас 36 цукерок і ви хочете розкласти їх порівну в кілька коробок без залишку, дільники 36 підкажуть можливі варіанти: 2, 3, 4, 6, 9, 12, 18 коробок.
У програмуванні класична задача — написати функцію, яка повертає список дільників. Оптимальний варіант українською мовою псевдокоду виглядає так:
функція знайти_дільники(n):
результат = []
для i від 1 до √n:
якщо n ділиться на i:
додати i
якщо i ≠ n/i:
додати n/i
повернути відсортований результат
Такий код працює за O(√n) і підходить для більшості практичних випадків.
Окремий випадок — пошук невідомого дільника в рівнянні виду a : x = b. Тут x = a : b. Це вже не пошук усіх дільників, а відновлення одного компонента ділення. Правило просте, але його часто плутають з пошуком невідомого діленого.
Коли варто скористатися калькулятором або програмою
Для чисел до 200–300 вручну працювати комфортно. Коли число перевищує кілька тисяч, а особливо коли воно багатоцифрове, розумніше використати онлайн-калькулятор або написати короткий скрипт. Сучасні мови програмування мають вбудовані або бібліотечні функції для факторизації, які справляються з числами до 10 за частки секунди.
Якщо задача вимагає знайти дільники кількох чисел одночасно або працювати з дуже великими значеннями (криптографічні модулі), краще звернутися до спеціалізованих бібліотек на кшталт sympy у Python чи GMP. У шкільних умовах достатньо звичайного калькулятора з функцією розкладу на множники або таблиці простих чисел.
Уміння знаходити дільники — це не просто шкільна навичка. Це спосіб бачити внутрішню структуру числа і швидко розв’язувати задачі, які на перший погляд здаються громіздкими. Оберіть метод відповідно до розміру числа: перебір для маленьких, пари через корінь для середніх, розклад на прості множники — коли потрібна повна картина або кількість дільників. Перевіряйте результат множенням, і помилок майже не буде.
