` 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973 `
Малая теорема Ферма даёт дополнительный критерий простоты для больших чисел: если \(p\) простое и \(p \nmid a\), то
\[ a^{p-1} \equiv 1 \pmod{p}. \]
На практике это означает: если для случайного \(a\) это сравнение не выполняется — число точно составное. Если выполняется — скорее всего простое (но не гарантировано: существуют числа Кармайкла, проходящие тест, но составные). Для задач ЕГЭ достаточно пробного деления по таблице.
Решето Эратосфена: составь таблицу сам
Решето Эратосфена позволяет построить таблицу простых чисел вручную — на черновике за несколько минут.
- Решето Эратосфена
- Шаг 1: Выписать все натуральные числа от 2 до N в строку (или таблицу).
- Шаг 2: Взять первое невычеркнутое число p — оно простое. Вычеркнуть все его кратные: 2p, 3p, 4p, … до N.
- Шаг 3: Перейти к следующему невычеркнутому числу и повторить шаг 2.
- Шаг 4: Остановиться, когда текущее простое p > √N. Все оставшиеся невычеркнутые числа — простые.
Пример для N = 50 (\(\sqrt{50} \approx 7{,}07\), поэтому достаточно дойти до простого 7).
Начальный ряд: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
p = 2. Вычёркиваем 4, 6, 8, 10, …, 50. Остаются нечётные плюс 2.
p = 3. Вычёркиваем оставшиеся кратные 3: 9, 15, 21, 27, 33, 39, 45.
p = 5. Вычёркиваем 25, 35 (остальные уже вычеркнуты).
p = 7. Вычёркиваем 49.
Следующее простое — 11 > 7,07, останавливаемся. Уцелевшие числа:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 — все 15 простых до 50.
Ключевой момент: вычёркивать кратные нужно начиная с \(p^2\), а не с \(2p\) — всё, что меньше \(p^2\), уже вычеркнуто на предыдущих шагах. Это ускоряет работу на черновике.
Забери шпаргалки по всем темам ЕГЭ
Формулы, методы и типовые ошибки — одним файлом в боте.
Как проверить, простое ли число: пробное деление
Чтобы проверить, является ли число \(N\) простым, достаточно делить его на все простые, не превосходящие \(\sqrt{N}\). Если ни одно из них не делит \(N\) без остатка — число простое.
Почему хватает \(\sqrt{N}\)? Если у \(N\) есть делитель \(d > \sqrt{N}\), то соответствующий частный \(N/d < \sqrt{N}\) тоже является делителем — и он был бы найден раньше. Поэтому пара «большой × маленький» не может ускользнуть от проверки.
Почему достаточно делить только на простые? Любое составное число само раскладывается в произведение меньших простых. Если \(N\) не делится ни на одно простое \(p \le \sqrt{N}\), оно не делится и ни на какое составное в этом диапазоне.
- Алгоритм пробного деления
- Шаг 1: Вычислить \(\lfloor\sqrt{N}\rfloor\) — верхнюю границу перебора.
- Шаг 2: Последовательно делить N на простые из таблицы: 2, 3, 5, 7, 11, …, не превышающие \(\sqrt{N}\).
- Шаг 3: Если нашёлся делитель — N составное; записать разложение.
- Шаг 4: Если ни один не подошёл — N простое.
Пример 1. Проверить, простое ли 137. \(\sqrt{137} \approx 11{,}7\) — проверяем простые 2, 3, 5, 7, 11.
- - 137 нечётное → не делится на 2.
- - \(1+3+7 = 11\), не делится на 3.
- - Не оканчивается на 0 или 5 → не делится на 5.
- - \(137 = 7 \cdot 19 + 4\) → не делится на 7.
- - \(137 = 11 \cdot 12 + 5\) → не делится на 11.
Вывод: 137 простое.
Пример 2. Проверить, простое ли 221. \(\sqrt{221} \approx 14{,}9\) — проверяем 2, 3, 5, 7, 11, 13.
- - \(221 = 13 \cdot 17\) → делится на 13.
Вывод: 221 составное, \(221 = 13 \cdot 17\).
Простые числа в задачах ЕГЭ и ОГЭ
Простые числа встречаются в трёх основных типах задач.
Тип 1. Количество делителей числа.
Задача: сколько натуральных делителей имеет число 720?
Решение по шаблону:
- 1. Разложить на простые: \(720 = 2^4 \cdot 3^2 \cdot 5^1\).
- 2. Применить формулу: \(\tau(720) = (4+1)(2+1)(1+1) = 30\).
Тип 2. НОД и НОК через разложение на простые.
Задача: найти НОД(504, 756) и НОК(504, 756).
- 1. \(504 = 2^3 \cdot 3^2 \cdot 7\), \quad \(756 = 2^2 \cdot 3^3 \cdot 7\).
- 2. \(\gcd = 2^{\min(3,2)} \cdot 3^{\min(2,3)} \cdot 7^{\min(1,1)} = 2^2 \cdot 3^2 \cdot 7 = 252\).
- 3. \(\operatorname{lcm} = 2^3 \cdot 3^3 \cdot 7 = 1512\).
- 4. Проверка: \(252 \cdot 1512 = 504 \cdot 756\) — верно.
Тип 3. Задачи на делимость с инвариантом.
Если простое \(p\) делит произведение \(bc\), то \(p \mid b\) или \(p \mid c\) (лемма Евклида). Это используется при доказательстве делимости в задачах номер 19.
Коротко
- НОД берётся по минимальным степеням общих простых множителей
- НОК берётся по максимальным степеням всех простых множителей
- Если p простое и p | bc, то p | b или p | c (лемма Евклида)
- Для составного делителя лемма не работает: 6 | 4·3, но 6 ∤ 4 и 6 ∤ 3
Типичные ошибки при работе с простыми числами
Частые вопросы
Является ли число 1 простым?
Нет. Единица не является ни простым, ни составным числом. По определению, простое число имеет ровно два натуральных делителя — единицу и само себя. У числа 1 делитель только один. Исторически 1 исключили из простых именно потому, что её включение разрушало бы единственность канонического разложения.
Сколько простых чисел до 1000?
До 1000 ровно 168 простых чисел. Последнее из них — 997.
Сколько простых чисел до 10 000?
До 10 000 ровно 1229 простых чисел. Последнее — 9973. Простые числа таблица до 10000 приведена выше в компактном формате, разбитом по тысячным диапазонам.
Как быстро проверить, простое ли число, без таблицы?
Вычислить \(\lfloor\sqrt{N}\rfloor\) и последовательно делить \(N\) на простые 2, 3, 5, 7, 11, 13, … до этой границы. Если ни одно не делит — число простое. Для \(N < 100\) хватает проверки на 2, 3, 5, 7; для \(N < 1000\) добавляем 11, 13, 17, 19, 23, 29, 31.
Что такое решето Эратосфена и как им пользоваться?
Метод последовательного вычёркивания кратных: берём наименьшее невычеркнутое число (оно простое), вычёркиваем все его кратные, переходим к следующему. Процесс заканчивается, когда текущее простое превышает \(\sqrt{N}\). На черновике удобно применять до 50–100: занимает 2–3 минуты и не требует таблицы.
Зачем знать простые числа для ЕГЭ по математике?
Каноническое разложение числа — основной инструмент задач на делители, НОД и НОК. Без умения быстро раскладывать числа на простые множители невозможно решить задания второй части на делимость: формула числа делителей \(\tau(n) = (\alpha_1+1)\cdots(\alpha_k+1)\) и связь \(\gcd \cdot \operatorname{lcm} = ab\) применяются только после того, как получено каноническое разложение.
По этой теме есть отдельный разбор: таблица квадратов чисел до 100.
По этой теме есть отдельный разбор: разложить число на простые множители.
По этой теме есть отдельный разбор: задание 19 ЕГЭ по теории чисел.
По этой теме есть отдельный разбор: задание 19 ЕГЭ математика база.
Забери шпаргалки по всем темам ЕГЭ
Формулы, методы и типовые ошибки — одним файлом в боте.