дозволяє знайти всі дільники числа і число дільників числа.
До початку страніциАлгорітм розкладання числа на прості множники
Щоб успішно впоратися із завданням розкладання числа на прості множники, потрібно дуже добре володіти інформацією статті прості і складені числа.
Суть процесу розкладання цілого позитивного і перевершує одиницю числа a зрозуміла з докази основної теореми арифметики. Сенс полягає в послідовному знаходженні найменших простих дільників p1, p2, ..., pn чисел a, a1, a2, ..., an-1. що дозволяє отримати ряд рівностей a = p1 · a1. де a1 = a: p1. a = p1 · a1 = p1 · p2 · a2. де a2 = a1: p2. ..., a = p1 · p2 · ... · pn · an. де an = an-1: pn. Коли виходить an = 1. то рівність a = p1 · p2 · ... · pn дасть нам шукане розкладання числа a на прості множники. Тут же слід зауважити, що p1≤p2≤p3≤ ... ≤pn.
Залишилося розібратися з перебуванням найменших простих дільників на кожному кроці, і ми будемо мати алгоритм розкладання числа на прості множники. Знаходити прості подільники нам допоможе таблиця простих чисел. Покажемо, як з її допомогою отримати найменший простий дільник числа z.
Послідовно беремо прості числа з таблиці простих чисел (2, 3, 5, 7, 11 і так далі) і ділимо на них дане число z. Перше просте число, на яке z розділиться без остачі, і буде його найменшим простим дільником. Якщо число z просте, то його найменшим простим дільником буде саме число z. Тут же слід нагадати, що якщо z не є простим числом, то його найменший простий дільник не перевищує числа. де - арифметичний квадратний корінь з z. Таким чином, якщо серед простих чисел, що не перевершують. не знайшлося жодного подільника числа z, то можна робити висновок про те, що z - просте число (більш докладно про це написано в розділі теорії під заголовком дане число просте або складене).
Для прикладу покажемо, як знайти найменший простий дільник числа 87. Беремо число 2. Ділимо 87 на 2, отримуємо 87: 2 = 43 (ост. 1) (якщо необхідно, дивіться статтю правила і приклади ділення цілих чисел із залишком). Тобто, при розподілі 87 на 2 виходить залишок 1, тому 2 - не є дільником числа 87. Беремо наступне просте число з таблиці простих чисел, це число 3. Ділимо 87 на 3, отримуємо 87: 3 = 29. Таким чином, 87 ділиться на 3 без остачі, отже, число 3 є найменшим простим дільником числа 87.
Зауважимо, що в загальному випадку для розкладання на прості множники числа a нам буде потрібно таблиця простих чисел до числа, не меншої, ніж. До цієї таблиці нам доведеться звертатися на кожному кроці, так що її потрібно мати під рукою. Наприклад, для розкладання на прості множники числа 95 нам буде достатньо таблиці простих чисел до 10 (так як 10 більше, ніж). А для розкладання числа 846 653 вже буде потрібна таблиця простих чисел до 1 000 (так як 1 000 більше, ніж).
Тепер ми володіємо достатніми відомостями, щоб записати алгоритм розкладання числа на прості множники. Алгоритм розкладання числа a такий:
Послідовно перебираючи числа з таблиці простих чисел, знаходимо найменший простий дільник p1 числа a, після чого обчислюємо a1 = a: p1. Якщо a1 = 1. то число a - просте, і вона сама є своїм розкладанням на прості множники. Якщо ж a1 на одно 1, то маємо a = p1 · a1 і переходимо до наступного кроку. Знаходимо найменший простий дільник p2 числа a1. для цього послідовно перебираємо числа з таблиці простих чисел, починаючи з p1. після чого обчислюємо a2 = a1: p2. Якщо a2 = 1. то шукане розкладання числа a на прості множники має вигляд a = p1 · p2. Якщо ж a2 на одно 1, то маємо a = p1 · p2 · a2 і переходимо до наступного кроку. Перебираючи числа з таблиці простих чисел, починаючи з p2. знаходимо найменший простий дільник p3 числа a2. після чого обчислюємо a3 = a2: p3. Якщо a3 = 1. то шукане розкладання числа a на прості множники має вигляд a = p1 · p2 · p3. Якщо ж a3 на одно 1, то маємо a = p1 · p2 · p3 · a3 і переходимо до наступного кроку. ... Знаходимо найменший простий дільник pn числа an-1. перебираючи прості числа, починаючи з pn-1. а також an = an-1: pn. причому an виходить дорівнює 1. Цей крок є останнім кроком алгоритму, тут отримуємо дані розкладання числа a на прості множники: a = p1 · p2 · ... · pn.
Всі результати, отримані на кожному кроці алгоритму розкладання числа на прості множники, для наочності представляють у вигляді такої таблиці, в якій зліва від вертикальної риси записують послідовно в стовпчик числа a, a1, a2, ..., an. а праворуч від смуги - відповідні найменші прості подільники p1, p2, ..., pn.
Залишилося лише розглянути кілька прикладів застосування отриманого алгоритму для розкладання чисел на прості множники.