Простото число е цяло число, по-голямо от 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 е сбор от две прости числа