Простые и составные числа. Разложение на простые множители
Простое число имеет ровно два натуральных делителя — единицу и само себя: \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \dots\) Составное число имеет больше двух делителей. Число 1 не относится ни к простым, ни к составным. Единственное чётное простое число — 2.
Основная теорема арифметики. Каждое натуральное число, большее 1, единственным образом (с точностью до порядка множителей) раскладывается в произведение простых чисел: \[n = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k}.\] Например, \(360 = 2^3 \cdot 3^2 \cdot 5\).
Как это работает. Разложим на простые множители число 1176.
- Делим на 2, пока делится: \(1176 = 2 \cdot 588 = 2 \cdot 2 \cdot 294 = 2 \cdot 2 \cdot 2 \cdot 147\).
- 147 на 2 не делится; сумма цифр \(1 + 4 + 7 = 12\) делится на 3: \(147 = 3 \cdot 49\).
- \(49 = 7 \cdot 7\). Итого \(1176 = 2^3 \cdot 3 \cdot 7^2\).
Ещё пример. Простое ли число 221?
Решение. Проверяем простые делители, не превосходящие \(\sqrt{221} \approx 14{,}9\): 2, 3, 5, 7, 11, 13. На 2, 3, 5 не делится (по признакам), \(221 : 7 = 31{,}57\dots\), \(221 : 11 = 20{,}09\dots\), \(221 : 13 = 17\). Ответ: нет, \(221 = 13 \cdot 17\).
Лайфхак. Чтобы проверить, простое ли число \(n\), достаточно перебрать простые делители до \(\sqrt{n}\): если у \(n\) есть делитель больше корня, то парный к нему делитель меньше корня и был бы найден раньше.
Из истории. Евклид около 300 года до н. э. доказал, что простых чисел бесконечно много: если бы их было конечное число, то произведение всех простых плюс единица не делилось бы ни на одно из них. Наибольшие известные простые числа сегодня содержат десятки миллионов цифр.
Закрепите теорию: 11 заданий с проверкой и подсказками, урок зачитывается от 70 %.
Пройти урок arrow_forward