Базовая математика: делимость, НОД, простые числа
Делимость, НОД и НОК, простые числа, решето Эратосфена и разложение на множители.
Числовая база олимпиадника — четыре темы.
1. Делимость и остатки. a делится на b, если a % b == 0. Остатки зациклены: последняя цифра числа — это n % 10, чётность — n % 2.
2. НОД и НОК. Наибольший общий делитель считается алгоритмом Евклида за O(log n) (вы писали его в курсе языка). Наименьшее общее кратное: НОК(a,b) = a / НОД(a,b) * b — именно в таком порядке, чтобы не переполниться.
3. Простые числа. Проверка одного числа — перебор делителей до корня. А если нужны ВСЕ простые до n — решето Эратосфена: выписываем числа и вычёркиваем кратные каждому простому.
Решето Эратосфена: все простые до n. Введите: 50
Почему решето быстрое: каждое составное число вычёркивается своими простыми делителями, суммарно получается O(n log log n) — почти линейно. Для n = 10⁷ работает меньше секунды.
Тонкость: вычёркивание начинается с i * i, а не с 2 * i — все меньшие кратные уже вычеркнуты меньшими простыми.
4. Разложение на простые множители: делим число на все делители до корня; если что-то осталось больше единицы — это последний простой множитель.
Разложение на простые множители. Введите: 360
Задание: с помощью решета посчитайте, сколько простых чисел меньше миллиона (ответ: 78498 — проверьте себя).
Затем решите прикреплённые задачи «НОД двух чисел», «Проверка простого числа» и «Факториал числа» — и отметьте урок пройденным.