Простые числа
Это понятие впервые встречается на программе «Инженерия и системный подход к решению задач» — примерно 11-12 лет (5-6 класс).
Числа, которые делятся нацело только на 1 и на себя: 2, 3, 5, 7, 11… Разложить их на меньшие множители нельзя.
12 кубиков складываются в прямоугольник (3 ряда по 4), а 7 — только в одну линию: простое число в прямоугольник не укладывается.
Выложить 6, 7 и 12 кубиков прямоугольниками в несколько рядов; назвать все простые числа до 20.
Числа с ровно двумя делителями. Любое целое больше 1 единственным образом раскладывается в произведение простых: 60 = 2·2·3·5 — простые служат «кирпичиками» всех остальных чисел. Все простые до N находит решето Эратосфена: выписать числа и вычеркнуть кратные каждого найденного простого.
Разложить 60 и 84 на простые множители; решетом Эратосфена найти все простые числа до 30.
Простых бесконечно много (доказал Евклид), с ростом N они встречаются реже. Ключевая асимметрия: перемножить два больших простых мгновенно, а разложить произведение обратно на множители — вычислительно трудно. На этом построено RSA-шифрование: открытый ключ содержит произведение двух секретных простых по сотни цифр каждое (RSA-2048 — число из 617 десятичных цифр).
Перемножить простые 61 и 53 (получается 3233 — быстро), затем разложить 3127 на два простых множителя, засекая время; сказать, какая операция легче и почему это годится для шифра.
Частое заблуждение
«1 — тоже простое число». Нет: у простого числа ровно два разных делителя — 1 и оно само; у единицы делитель один, поэтому она не простая и не составная.