Коли ви стикаєтеся з числом 24 і знаєте, що частка дорівнює 6, невідомий дільник ховається просто за прямим діленням: 24 поділити на 6 дає чіткі 4. Цей трюк здається елементарним, але саме з нього розпочинається вся магія пошуку дільників – від шкільних задач до розгадування таємниць криптографії. Дільник числа – це будь-яке ціле, яке ділить його без остачі, і знати, як його викопати з-під шару цифр, перетворює математику на справжню пригоду.
Уявіть величезне число, скажімо, продукт двох простих близнюків, і завдання – розщепити його на частини. Початківці часто починають із перевірки малих чисел, а просунуті гравці вдаються до хитрих алгоритмів, що працюють на суперкомп’ютерах. Розберемо все по поличках, від бази до глибин, з прикладами, які ви зможете повторити самі.
Базовий рівень: правило для шкільних рівнянь ділення
У початковій школі невідомий дільник з’являється в простих виразах на кшталт 30 : ? = 5. Тут панує одне залізне правило: дільник дорівнює діленому, поділеному на частку. 30 / 5 = 6 – і вуаля, готово. Це випливає з властивостей ділення як оберненого множення, де все зводиться до перевірки: 6 × 5 справді дає 30?
Але життя не обмежується табличками множення. Візьмімо складніший приклад: 48 : ? = 8. Швидко: 48 / 8 = 6. Щоб закріпити, розберемо на групи – уявіть 48 яблук, розподілених по 8 у кожній групі: виходить рівно 6 груп. Такий підхід робить математику живою, ніби ви рахуєте реальні речі в саду.
Для початківців ключ – практика з перевіркою. Перед списком кроків ось вступ: ось як систематизувати процес.
- Визначте відомі частини: ділене і частку.
- Поділіть ділене на частку – отримайте кандидата на дільник.
- Перевірте множенням: чи дає воно назад ділене без остачі.
- Якщо остача є, перегляньте розрахунок – помилки ховаються в арифметиці.
Цей метод блискучий для чисел до сотень, але для більших числах перехід до наступного рівня неминучий. Він закладає фундамент, на якому будується все інше, перетворюючи хаос цифр на впевнену логіку.
Знаходження всіх дільників: метод перебору для середнього рівня
Тепер забудьте про готову частку – уявіть, що вам дали просто число 36, і потрібно перелічити всіх його дільників. Почніть з малого: 1 завжди ділить, 2 теж (парне), 3 (сума цифр 9 ділиться на 3), 4 (36/4=9), 6, 9, 12, 18, 36. Повний список: 1, 2, 3, 4, 6, 9, 12, 18, 36. Секрет ефективності – не перебирати все підряд, а йти до квадратного кореня числа.
Чому до sqrt(36)=6? Бо якщо d ділить n, то й n/d теж. Перевіряйте пари: знайшли 4, додайте 36/4=9. Це економить час удвічі. Для 315: sqrt≈17.7, перевірте 2 (ні), 3 (315/3=105, так), потім факторизуйте 105: 3 (35), 5 (7), 7. Дільники: 1,3,5,7,9,15,21,35,45,63,105,315.
Ось структурований алгоритм trial division – класичний метод перебору.
- Виключіть 1 і саме число для нетривіальних.
- Перевірте 2 окремо (для парних).
- Для непарних від 3 до sqrt(n) з кроком 2: якщо n % i == 0, i – дільник, додайте пару n/i.
- Сортуйте список для зручності.
Цей підхід блискавичний для чисел до мільйонів – на калькуляторі секунди. Але для 10^12? Години на руках, хвилини на комп’ютері. Перехід до оптимізації стає неминучим, бо математика любить хитрість.
Оптимізація пошуку: сито Ератосфена та його варіації
Коли дільників потрібно багато, для діапазону чисел, сито Ератосфена перетворює перебор на елегантний танець. Воно знаходить прості числа до n, а отже, й потенційні дільники. Почніть з масиву від 2 до n, викресліть кратні 2, потім 3, 5… Залишки – прості, їх множники дають дільники.
Для одного числа адаптуйте: генеруйте прості до sqrt(n) ситом, потім пробуйте тільки їх. Ефективність злітає – замість тисяч перевірок десятки. Приклад для 100: прості до 10: 2,3,5,7. Швидко знаходимо всі дільники.
У реальному житті це рятує в програмуванні. Python-код спростить:
def divisors(n):
divs = set()
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divs.add(i)
divs.add(n//i)
return sorted(divs)Такий код видає список миттєво. Але для гіганів – час на алгоритми наступного рівня.
Просунуті алгоритми: Ферма і Поллард-Ро для великих чисел
Метод Ферма сяє, коли прості множники близькі: n = p*q, де p≈q. Ідея – n = x² – y² = (x-y)(x+y). Почніть x = ceil(sqrt(n)), шукайте y² = x² – n квадратне. Приклад: n=5959, sqrt≈77.23, x=78: 78²=6084, 6084-5959=125 (не sq), x=79:6241-5959=282 ні, x=82:6724-5959=765=27.7² ні, аж до x=91:8281-5959=2322? Чекайте, класичний приклад знаходить 77*79? Ні, 5959=59*101. Ферма знаходить за кілька кроків, бо 101-59=42, sqrt(n)≈77, x=(59+101)/2=80, y=21.
Швидко для близьких множників, повільно інакше. Тепер Поллард-Ро – ймовірнісний геній для середніх чисел (до 10^20). Використовує псевдовипадкову послідовність x_{i+1} = (x_i² + c) mod n, виявляє цикл за Флойдом (черепаха-зайчик), НСД(|x_i – x_j|, n) – дільник.
Приклад для 8051: c=1, x0=2. Послідовність циклічно повторюється, НСД дає 8051=83*97. У Python це реалізовано в бібліотеках sympy, але базовий код – 20 рядків дива.
| Алгоритм | Складність | Краще для | Приклад n |
|---|---|---|---|
| Trial division | O(√n) | Малі n < 10^12 | 315 → 3×5×3×7 |
| Сито Ератосфена | O(n log log n) | Діапазони | Прості до 10^6 |
| Ферма | O(√(n/4)) | Близькі p,q | 5959 → 59×101 |
| Поллард-Ро | O(n^{1/4}) | 10^10 – 10^20 | 8051 → 83×97 |
Джерела даних: uk.wikipedia.org (Факторизація цілих чисел).
Ці алгоритми – місток до елітних методів як GNFS для RSA-чисел.
Типові помилки при пошуку невідомого дільника
Початківці забувають перевіряти до sqrt(n), витрачаючи час на зайве. Просунуті ігнорують оптимізацію для парних – починайте з 2! Ще пастка: в Поллард-Ро погано вибраний c веде до провалу, міняйте на 1,2,3. Не забувайте рекурсію – знайшли d, факторизуйте n/d. І найгірше: плутанина з НСД/НСК, бо дільники числа не завжди спільні.
Факторизація в криптографії: чому дільники ховають мільярди
RSA тримається на труднощі факторизації n=p*q, де p,q ~10^150. Рекорд – RSA-250 (829 бітів) факторизовано 2020-го GNFS на тисячах ядер. Станом на 2026, 1024-бітні RSA безпечні класично, але квантові загрожують Шором. Уявіть: зламайте ключ – розкрийте паролі світу.
Практика: генеруйте RSA n=17*23=391, факторизуйте Поллардом. Застосування скрізь – від HTTPS до блокчейну. Ви не повірите, але ваш банківський PIN частково залежить від цих алгоритмів.
У повсякденні шукайте дільники для оптимізації: НСД для скорочення дробів (алгоритм Евкліда), множники для кодів. Спробуйте на 2026: дільники 1,2,1013. Експериментуйте в Python – математика оживає в коді.
З цими інструментами ви розкопаєте будь-який дільник, від шкільного до космічного. А що, якщо наступне число – ваше?
About the Author
