Простое число — это целое число больше 1, имеющее ровно два делителя: 1 и само себя. Простые числа являются строительными блоками всех целых чисел: каждое целое число можно выразить как произведение простых чисел.

Первые 25 простых чисел

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Обратите внимание, что 2 — единственное четное простое число. Все остальные четные числа делятся на 2.

Метод 1: Пробное разделение

Самый простой способ проверить, является ли число простым — проверить, делит ли его целое число до квадратного корня.

Ключевая мысль: Если n имеет коэффициент больше √n, то у него также есть соответствующий коэффициент меньше √n. Поэтому вам нужно проверить только до √n.

Алгоритм:

  1. Если n < 2, не простое число
  2. Если n = 2, заштриховать
  3. Если n четное (кроме 2), не простое
  4. Проверьте все нечетные числа от 3 до √n.
  5. Если есть, разделите n поровну, а не просто
  6. В противном случае просто

Пример: является ли 97 простым?

√97 ≈ 9,85, поэтому проверьте простые числа до 9: 2, 3, 5, 7.

  • 97 ÷ 2 = 48,5 (не целое)
  • 97 ÷ 3 = 32,33... (не целое)
  • 97 ÷ 5 = 19,4 (не целое)
  • 97 ÷ 7 = 13,86 (не целое)

Делители не найдены — 97 — простое число.

Пример: является ли 91 простым?

√91 ≈ 9,54, проверьте до 9: 2, 3, 5, 7

  • 91 ÷ 7 = 13 (целое число!)

91 не простое число — 91 = 7 × 13.

Способ 2: Решето Эратосфена

Решето Эратосфена находит все простые числа до заданного предела. Это быстрый и элегантный способ, изобретенный греческим математиком Эратосфеном около 240 г. до н.э.

Чтобы найти все простые числа до 50:

  1. Выпишите цифры от 2 до 50.
  2. Начните с 2 (первое простое число). Вычеркните все числа, кратные 2 (4, 6, 8...).
  3. Перейти к следующему неперечеркнутому числу: 3. Вычеркнуть кратные 3 (9, 15, 21...)
  4. Следующее не зачеркнутое: 5. Зачеркнуть кратное 5 (25, 35...)
  5. Следующие неперечеркнутые: 7. Зачеркнуть кратные 7 (49...)
  6. Остановитесь, когда достигнете √50 ≈ 7,07.
  7. Все оставшиеся неперечеркнутые числа простые.

Простое число до 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Простые числа до 100: полный список

Диапазон Простые числа
1–10 2, 3, 5, 7
11–20 11, 13, 17, 19
21–30 23, 29
31–40 31, 37
41–50 41, 43, 47
51–60 53, 59
61–70 61, 67
71–80 71, 73, 79
81–90 83, 89
91–100 97

Ниже 100 существует 25 простых чисел.

Быстрые тесты на делимость

Прежде чем делать полное деление, ознакомьтесь с этими правилами:

Делится на Если...
2 Последняя цифра четная (0,2,4,6,8)
3 Сумма цифр, кратная 3
5 Последняя цифра 0 или 5
7 Нет простого правила — просто разделите
11 Сумма чередующихся цифр, кратная 11

Пример: является ли число 143 простым?

  • Даже нет ✓
  • 1+4+3 = 8, не делится на 3 ✓
  • Не заканчивается на 0 или 5 ✓
  • √143 ≈ 11,96, проверьте до 11
  • 143 ÷ 7 = 20,43 ✓
  • 143 ÷ 11 = 13 — делится!

143 = 11 × 13. Не простое число.

Почему простые числа имеют значение

Криптография. Шифрование RSA, используемое для защиты интернет-банкинга, HTTPS и электронной почты, основано на том факте, что умножить два больших простых числа легко, но разложить результат обратно на простые числа чрезвычайно сложно.

Информатика. Хеш-таблицы, генераторы случайных чисел и контрольные суммы используют свойства простых чисел.

Чистая математика. Распределение простых чисел остаётся одной из самых глубоких нерешённых проблем математики — гипотезой Римана.

Интересные факты

  • Самое большое известное простое число (по состоянию на 2024 год) имеет более 41 миллиона цифр. — Простые числа-близнецы — это простые числа, отличающиеся на 2 (11 и 13, 17 и 19, 41 и 43).
  • Существует бесконечно много простых чисел. Это доказал Евклид около 300 г. до н.э.
  • Гипотеза Гольдбаха (недоказанная с 1742 года): каждое четное число > 2 является суммой двух простых чисел.

Читать дальше