Таблица простых чисел

Что такое простое число

Простое число — натуральное число больше единицы, у которого ровно два делителя: 1 и оно само. Например, 7 делится только на 1 и на 7. Число с большим количеством делителей называют составным: 12 делится на 1, 2, 3, 4, 6 и 12. Единица — ни простое, ни составное: у неё один делитель.

Простые числа — «атомы» умножения. По основной теореме арифметики любое натуральное число больше 1 раскладывается в произведение простых, и это разложение единственно, если не считать порядка множителей: 360 = 2³ · 3² · 5, и по-другому разложить 360 на простые нельзя. Поэтому единицу и не относят к простым — иначе разложений было бы бесконечно много: 360 = 1 · 2³ · 3² · 5 = 1 · 1 · 2³ · 3² · 5…

Простые числа до 100

Их 25 — эту строку полезно помнить наизусть, она нужна для проверки делимости и разложения на множители:

Среди них только одно чётное — 2. Все остальные простые числа нечётные: любое чётное число больше 2 делится на 2.

Таблица простых чисел до 1000

По сотням: чем дальше от нуля, тем реже встречаются простые числа — в первой сотне их 25, в десятой — 14.

Как проверить, простое ли число

Достаточно попробовать разделить число на простые числа, не превосходящие квадратного корня из него. Если у N есть делитель больше √N, парный ему делитель N / d меньше √N — и он нашёлся бы раньше. Например, √97 ≈ 9,8, поэтому проверяем 2, 3, 5, 7: ни одно из них 97 не делит, значит, 97 — простое. А для 91 перебор останавливается на семёрке: 91 = 7 · 13. Деление на 2, 3, 5, 7 и 11 часто можно заменить признаками делимости — по последней цифре, по сумме цифр и так далее.

Для чисел в десятки цифр перебор слишком долгий, и калькулятор на этой странице использует тест Миллера — Рабина. Он проверяет специальное условие для нескольких оснований; если число его не выполняет — оно точно составное. Для чисел меньше 3,3 · 10²⁴ проверка по первым 13 простым основаниям (от 2 до 41) даёт гарантированный ответ, для больших — вероятностный, с исчезающе малой ошибкой. Множители больших чисел калькулятор ищет ро-методом Полларда.

Решето Эратосфена

Чтобы получить все простые числа до N, древнегреческий математик Эратосфен предложил просеивать ряд чисел. Выпишите числа от 2 до N. Первое невычеркнутое — 2 — простое; вычеркните все его кратные. Следующее невычеркнутое — 3 — простое; вычеркните кратные 3. Повторяйте, пока квадрат очередного простого не станет больше N: оставшиеся числа — простые. Для N = 100 хватает четырёх шагов — 2, 3, 5 и 7, потому что 11² = 121 > 100. Нажмите «Начать» в блоке выше, чтобы пройти шаги самостоятельно.

Вычёркивать кратные p можно начинать с p²: все меньшие кратные уже вычеркнуты на предыдущих шагах как кратные меньших простых.— Правило

Сколько простых чисел

Бесконечно много. Доказательство есть в «Началах» Евклида: если бы простых было конечное число, их произведение плюс единица не делилось бы ни на одно из них — и имело бы другой простой делитель. Например, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30 031 = 59 · 509: 59 и 509 — простые, которых не было в исходном списке.

При этом простые числа встречаются всё реже. Их количество до x примерно равно x / ln x: до 100 формула даёт 22 (на самом деле 25), до 1000 — 145 (на самом деле 168), до 10 000 — 1 086 (на самом деле 1 229). Отношение стремится к единице — это теорема о распределении простых чисел.

Пары простых, отличающихся на 2, называют близнецами: 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31. До 1000 таких пар 35, последняя — 881 и 883. Бесконечно ли их много — одна из самых известных открытых задач математики.

Разложение на простые множители

Любое составное число раскладывается на простые множители: делите его на наименьший простой делитель, пока не получится единица. Разложение помогает находить делители, наибольший общий делитель и наименьшее общее кратное. Подробные разборы для частых школьных чисел — ниже, от 12 до 3600: столбиком, деревом, все делители и их сумма. На трудности разложения очень больших чисел на множители основана криптография с открытым ключом RSA.