Як швидко знайти дільники натуральної кількості без залишку
Знаходження дільників натурального числа без залишку є поширеним завданням для тих, хто вивчає програмування. На різних форумах можна побачити теми про те, як реалізувати цей алгоритм такими мовами як C, C++ або C#. Ось приклад цього алгоритму.
Не дивлячись на те, що завдання є простим, дана реалізація є невдалою 😟. Пояснюю чому.
Допустимо потрібно визначити всі дільники без залишку для числа 528.
Його дільники є числа: 1, 2, 3, 4, 6, 8, 11, 12, 16, 22, 24, 33, 44, 48, 66, 88, 132, 176, 264 і 528. Для того щоб визначити ці числа необхідно виконати 528 ітерацій у циклі. Зважаючи на факт того, що після числа 528 найближчим дільником є число 264 — половина ітерацій йдуть марно. Залишається друга половина ітерація від 264 до 1, але й тут більшість ітерацій йде марно. З 264 можливих варіанти підходять лише 19 - це: 264, 176, 132, 88, 66, 48, 44, 33, 24, 22, 16, 12, 11, 8, 6, 4, 3, 2, 1.
На превеликий подив, наші 20 «правильних» ітерацій, які дають 20 чисел для відповіді, можна скоротити наполовину. Зважаючи на те, що час поділу дільник і приватне доповнюють один одного. Як тільки знайшли дільник без залишку, приватне висловлювання теж є дільником без залишку:
- 528 ділиться на 528, виходить 1,
- 528 ділиться на 264, виходить 2,
- 528 ділиться на 176, виходить 3
- і так далі
Можна оптимізувати поточний код, додавши до нього умови, але що б цього не робити на допомогу приходить факторизація!
Шляхом не хитрих маніпуляцій отримуємо такі функції, щоб протестувати виграш від нового рішення. Функція divisor знаходить дільники числа без залишку з допомогою перебору. Афункція divisor_by_factorization знаходить дільники числа без залишку за допомогою факторизації.
Тепер протестуємо наші функції даних. Шлях обидва алгоритми обчислять дільники без залишку ряду чисел від 10 до 25 000.
Підсумки виходять такі. Для методу перебору потрібно 18 секунд. А за допомогою факторизації виконання алгоритму зайняло всього 0.9 секунд. Це в 20 разів ефективніше, ніж звичайним перебором.