Інформатика – Поглиблений рівень

Прочитайте!

Факторизацією натурального числа називають його розкладання на добуток простих множників.

Наприклад, число 525 може бути розкладене на такі прості множники: 3*5*5*7 = 525. Доведено, що кожне натуральне число має єдине розкладання на прості множники.
Тривіальним алгоритмом факторизації чисел є повний перебір можливих простих дільників, починаючи з числа 2. Його сутність така.

Пояснимо сутність факторизації методом повного перебору на прикладі 1.

Приклад 1. Розглянемо сутність методу повного перебору на прикладі числа 84.

1. Визначаємо, що число 84 непросте, тому ділимо це число на 2. Отримаємо частку 42 і перший дільник 2.
2. Визначаємо, що число 42 непросте, тому ділимо його на 2. Отримаємо частку 21 і другий дільник 2.
3. Визначаємо, що число 21 непросте, тому робимо спробу поділити його на найменший дільник 2. Але число 21 не ділиться на 2. Тому переходимо до наступного простого числа.
4.  Ділимо число 21 на 3. Отримаємо частку 7 і третій дільник 3.
5.  Визначаємо, що число 7 просте. Тому четвертим простим дільником є 7. На цьому процес факторизації завершений. Отже, число 84 можна розкласти на такі прості множники: 2*2*3*7 = 84.

З описаного алгоритму можна зробити висновок, що для факторизації чисел натурального ряду методом повного перебору треба:

• уміти визначати, чи є частка на кожному кроці факторизації простим числом;
• уміти визначати черговий за величиною простий дільник.

На практиці прості числа деякого діапазону інколи зберігаються в таблиці (масиві, списку). Сутність алгоритму розкладання цілого числа на прості множники з використанням масиву простих чисел шляхом повного перебору така:

Приклад 2. Програму реалізації алгоритму зображено:

Приклад 3. Розглянемо більш удосконалену програму факторизації натуральних чисел методом повного перебору, але без використання масиву простих чисел. У програмі використано ключове слово yield, яке виконує фактично ту ж функцію, що й return (повертає результат обчислення). У цьому випадку значення d передається у чергову позицію списку.

Самостійне виконання вправу

Практична робота “Основні поняття теорії чисел”

Завдання 1 (2 бали). Переведіть числа 345, 674 у двійкову систему числання.

Завдання 2 (2 бали). Переведіть числа 1101101, 11000111 з двійкової в десяткову систему числення.

Завдання 3 (2 бали). Виконайте задачу Приклад 2.

Завдання 4 (2 бали). Виконайте задачу Приклад 3.

Завдання 5 (2 бали). Розробіть таблицю виконання алгоритму факторизації числа 40 на основі методу повного перебору.

Самостійне розв’язання задач

Задача 1. Обчислити 7¹⁰. Вивести лише кількість цифр результату. Де 7 і 10 – це довільні числа не більші 100, які вводяться з клавіатури.

Задача 2. Обчислити факторіал числа n (n ≤ 50). Вивести суму цифр числа n!.

Задача 3. Користувач вводить велике число. Знайти найбільшу цифру в ньому.

Задача 4. Користувач вводить велике число. Знайти найменшу цифру в ньому.

Задача 5. Напишіть програму, яка перевірить чи введене користувачем число ділиться націло на 2 і на 5.

Задача 6. Напишіть програму, яка перевірить чи введене користувачем число ділиться націло на 2 і на 10.

Задача 7. Напишіть програму, яка перевірить чи введене користувачем п’ятицифрове число  ділиться націло на 3.

Задача 8. Напишіть програму, яка перевірить чи введене користувачем п’ятицифрове число  ділиться націло на 9.

Задача 9. Напишіть програму, яка перевірить чи введене користувачем п’ятицифрове число  ділиться націло на 3 і на 2.

Задача 10. Напишіть програму для перетворення відстані (вказана у футах) у дюйми (1 фут = 12 дюймів), ярди (1 фут = 0,333333333 ярда) і милі (1 фут = 0,000189393939 милі).

Задача 11. Знайдіть найбільший спільний дільник (НСД) для двох  чисел (числа не більші ніж 10000)