Простые числа: таблица значений и алгоритмы проверки
Простое число — это натуральное число больше 1, которое делится только на 1 и на само себя. Чтобы быстро определить, является ли число простым, достаточно проверить его делимость на простые числа до квадратного корня из этого числа. Для диапазона до 100 удобнее всего использовать готовую таблицу или метод «решета Эратосфена».
Готовая таблица простых чисел (до 100)
В диапазоне от 1 до 100 содержится ровно 25 простых чисел. Эта таблица покрывает большинство бытовых и школьных задач.
| Десятки | Простые числа в диапазоне |
|---|---|
| 0–9 | 2, 3, 5, 7 |
| 10–19 | 11, 13, 17, 19 |
| 20–29 | 23, 29 |
| 30–39 | 31, 37 |
| 40–49 | 41, 43, 47 |
| 50–59 | 53, 59 |
| 60–69 | 61, 67 |
| 70–79 | 71, 73, 79 |
| 80–89 | 83, 89 |
| 90–99 | 97 |
Важно: Число 1 не является ни простым, ни составным. Число 2 — единственное чётное простое число. Все остальные чётные числа делятся на 2, поэтому они составные.
Как составить таблицу самостоятельно: Решето Эратосфена
Если вам нужен список простых чисел для большего диапазона (например, до 1000), строить его вручную перебором долго. Используйте алгоритм решета Эратосфена. Он позволяет отсеять все составные числа, оставив только простые.
Пошаговый алгоритм
- Выпишите ряд чисел от 2 до $N$ (верхней границы вашего диапазона).
- Возьмите первое число (это 2) и вычеркните из списка все числа, кратные ему (4, 6, 8, 10...), кроме самого двойки.
- Найдите следующее незачёркнутое число (это будет 3). Вычеркните все числа, кратные ему (9, 15, 21...), кроме самой тройки. (Чётные кратные 3 уже вычеркнуты на предыдущем шаге).
- Повторяйте процесс: берите следующее незачёркнутое число ($p$) и вычёркивайте его кратные ($p^2, p^2+p, ...$).
- Остановитесь, когда квадрат текущего простого числа превысит $N$ ($p^2 > N$).
Все числа, которые остались незачёркнутыми, являются простыми.
Оптимизация: При вычёркивании кратных для числа $p$ начинайте не с $2p$, а с $p^2$. Все меньшие кратные ($2p, 3p...$) уже были вычеркнуты на этапах работы с меньшими простыми числами.
Как быстро проверить одно число на простоту
Строить таблицу ради проверки одного числа неэффективно. Используйте метод последовательного деления.
Алгоритм ручной проверки
Чтобы проверить число $n$:
- Если $n < 2$, оно не простое.
- Если $n = 2$ или $n = 3$, оно простое.
- Если $n$ делится на 2 или на 3, оно составное.
- Перебирайте потенциальные делители $d$, начиная с 5, с шагом до $\sqrt{n}$.
- Проверьте делимость на $d$.
- Проверьте делимость на $d + 2$.
- Увеличьте $d$ на 6 и повторите.
Почему это работает? Любое простое число больше 3 имеет вид $6k \pm 1$. Поэтому нет смысла проверять деление на числа вида $6k, 6k+2, 6k+3, 6k+4$ — они гарантированно делятся на 2 или 3.
Пример: Проверка числа 97
- Находим $\sqrt{97} \approx 9.8$. Значит, нужно проверить делители до 9.
- Делится ли на 2? Нет (нечётное).
- Делится ли на 3? Сумма цифр $9+7=16$, на 3 не делится.
- Проверяем следующие кандидаты по формуле $6k \pm 1$:
- $k=1 \rightarrow 5$ и $7$.
- $97 : 5$ — не делится (не оканчивается на 0 или 5).
- $97 : 7 = 13$ (остаток 6) — не делится.
- Следующий кандидат $11$ уже больше $\sqrt{97}$.
- Вывод: 97 — простое число.
Сравнение методов
| Метод | Когда применять | Плюсы | Минусы |
|---|---|---|---|
| Готовая таблица | Числа до 100–1000 | Мгновенный ответ | Требует памяти или шпаргалки |
| Решето Эратосфена | Нужен список всех простых чисел в диапазоне | Системный подход, исключает пропуски | Трудоёмко для одиночных проверок |
| Деление до $\sqrt{n}$ | Проверка одного конкретного числа | Не требует подготовки | Медленно для очень больших чисел |
Частые ошибки при работе с простыми числами
- Считать 1 простым числом. Единица имеет только один делитель (саму себя), а определение простого числа требует ровно двух различных делителей.
- Считать 9, 15, 21 простыми. Эти числа нечётные, но делятся на 3. Нечётность — необходимое, но недостаточное условие простоты.
- Проверять делители до самого числа $n$. Это лишняя трата времени. Достаточно проверить делители до $\sqrt{n}$. Если у числа есть делитель больше корня, то обязательно есть парный ему делитель меньше корня.
- Забывать число 2. Часто начинают проверку только с нечётных делителей, забывая, что чётные числа (кроме 2) сразу являются составными.
FAQ
Какое самое большое простое число до 100? 97.
Является ли число 51 простым? Нет. $5 + 1 = 6$, значит, число делится на 3 ($51 = 17 \times 3$).
Почему нельзя использовать таблицу простых чисел «до бесконечности»? Простых чисел бесконечно много (это доказал ещё Евклид). Составить полную таблицу невозможно, можно лишь вычислить простые числа в заданном конечном диапазоне.
Как быстро проверить трёхзначное число? Найдите его квадратный корень (для 999 это $\approx 31.6$). Проверьте делимость на простые числа до 31: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Если ни на одно не делится — число простое.