Просте число — це ціле число, більше за 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.
Алгоритм:
- Якщо n < 2, не простий
- Якщо n = 2, штрих
- Якщо n парне (крім 2), не просте
- Перевірте всі непарні числа від 3 до √n
- Якщо є, розділіть n порівну, а не простим числом
- В іншому випадку простим числом
Приклад: чи є 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:
- Випишіть числа від 2 до 50
- Почніть з 2 (перший простий). Викресліть усі кратні 2 (4, 6, 8...)
- Перейти до наступного незакресленого числа: 3. Викреслити кратне 3 (9, 15, 21...)
- Наступне незакреслене: 5. Викресліть кратні 5 (25, 35...)
- Наступне незакреслене: 7. Викресліть кратне 7 (49...)
- Зупиніться, коли досягнете √50 ≈ 7,07
- Усі незакреслені числа, що залишилися, є простими
Штрихи до 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 |
Є 25 простих чисел нижче 100.
Швидкі тести на подільність
Перед повним поділом перевірте ці правила:
| Ділиться на | якщо... |
|---|---|
| 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 є сумою двох простих чисел