Простые числа до 1000
Таблица всех простых чисел от 2 до 997 по сотням, количество простых чисел до 10, 100, …, 10 000 000 в сравнении с асимптотическим законом, решето Эратосфена, признаки делимости, простые близнецы, простые числа Мерсенна и роль простых чисел в криптографии.
Простое число — натуральное число больше 1, которое делится только на 1 и на себя. Число 1 не считается ни простым, ни составным. Любое натуральное число больше 1 раскладывается на простые множители единственным образом (основная теорема арифметики): 360 = 2³·3²·5.
Простые числа до 1000
| Интервал | Простые числа | Сколько |
|---|---|---|
| 0–99 | 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 | 25 |
| 100–199 | 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 | 21 |
| 200–299 | 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293 | 16 |
| 300–399 | 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397 | 16 |
| 400–499 | 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499 | 17 |
| 500–599 | 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599 | 14 |
| 600–699 | 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691 | 16 |
| 700–799 | 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797 | 14 |
| 800–899 | 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887 | 15 |
| 900–999 | 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 | 14 |
Всего до 1000 — 168 простых чисел. Единственное чётное простое число — 2; все остальные нечётны, а начиная с 5 имеют вид 6k ± 1.
Как проверить, простое ли число
Достаточно проверить делимость на простые числа, не превосходящие √n. Например, для 221: √221 ≈ 14,9, проверяем 2, 3, 5, 7, 11, 13 — делится на 13 (221 = 13·17), значит, составное. Для чисел до 1000 хватает делителей до 31.
| Делитель | Признак делимости |
|---|---|
| 2 | последняя цифра чётная |
| 3 | сумма цифр делится на 3 |
| 5 | последняя цифра 0 или 5 |
| 7 | удвоенная последняя цифра, вычтенная из числа без неё, делится на 7: 343 → 34 − 6 = 28 |
| 11 | знакочередующаяся сумма цифр делится на 11: 1331 → 1 − 3 + 3 − 1 = 0 |
| 13 | учетверённая последняя цифра, прибавленная к числу без неё, делится на 13: 221 → 22 + 4 = 26 |
Решето Эратосфена находит все простые до N: выписываем числа 2…N, берём первое невычеркнутое число p, вычёркиваем все его кратные начиная с p², повторяем, пока p² ≤ N. Невычеркнутые числа — простые.
Сколько всего простых чисел
Простых чисел бесконечно много (доказательство Евклида: если бы их было конечное число, произведение всех плюс 1 не делилось бы ни на одно из них). Чем дальше, тем реже они встречаются: по асимптотическому закону распределения количество простых до x примерно равно x / ln x.
| x | π(x) — простых до x | x / ln x | x / π(x) |
|---|---|---|---|
| 101 | 4 | 4 | 2,50 |
| 102 | 25 | 22 | 4,00 |
| 103 | 168 | 145 | 5,95 |
| 104 | 1 229 | 1086 | 8,14 |
| 105 | 9 592 | 8686 | 10,43 |
| 106 | 78 498 | 72382 | 12,74 |
| 107 | 664 579 | 620421 | 15,05 |
Последний столбец показывает средний промежуток между соседними простыми: около ln x.
Особые виды простых чисел
- Простые близнецы — пары, отличающиеся на 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103)… Бесконечно ли их много, до сих пор неизвестно.
- Простые Мерсенна — вида 2ᵖ − 1: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647 (p = 2, 3, 5, 7, 13, 17, 19, 31). Показатель p обязан быть простым, но этого недостаточно: 2¹¹ − 1 = 2047 = 23·89. Самые большие известные простые числа — числа Мерсенна.
- Простые Ферма — вида 2^(2ⁿ) + 1: 3, 5, 17, 257, 65537. Других простых Ферма не найдено. Число 65537 часто используют как открытую экспоненту в RSA.
- Числа Софи Жермен — простые p, для которых 2p + 1 тоже простое: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89… Используются при выборе параметров протокола Диффи — Хеллмана.
Простые числа в криптографии
Перемножить два больших простых числа легко, а разложить произведение обратно на множители — чрезвычайно трудно. На этой асимметрии построен алгоритм RSA: открытый ключ содержит n = p·q, а секретный вычисляется через p и q. В реальных ключах p и q имеют по 1024 бита и больше (около 300 десятичных цифр). Попробовать алгоритм на маленьких числах можно в калькуляторе RSA, а остатки и обратные по модулю посчитать в калькуляторе модульной арифметики.
Комментарии и вопросы