Справочник по простым числам: таблицы и алгоритмы проверки

Простое число — это натуральное число больше единицы, которое не имеет положительных делителей, кроме 1 и самого себя. Чтобы быстро определить, является ли число простым, достаточно проверить его делимость на все простые числа вплоть до квадратного корня из этого числа. Ниже представлены готовые таблицы простых чисел и эффективные методы их вычисления.

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

Для быстрой работы с небольшими числами удобнее всего использовать справочные списки. Единица (1) не является ни простым, ни составным числом.

Список всех простых чисел от 1 до 100

В первой сотне содержится ровно 25 простых чисел. Это базовый набор, который полезно знать для устного счета и решения школьных задач.

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

В диапазоне от 1 до 1000 находится 168 простых чисел. Приводим список чисел, следующих за первой сотней, сгруппированных для удобства восприятия.

От 100 до 200: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

От 200 до 300: 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293.

От 300 до 400: 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397.

От 400 до 500: 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499.

От 500 до 1000 (выборочно): 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.

Как самостоятельно проверить число на простоту

Если числа нет в таблице, его можно проверить вручную или с помощью алгоритма. Выбор метода зависит от размера числа.

Метод 1: Перебор делителей до квадратного корня

Это универсальный способ для чисел средней величины (до миллионов и выше).

Алгоритм действий:

1. Если число $n \le 1$, оно не простое.
2. Если $n = 2$ или $n = 3$, оно простое.
3. Если $n$ делится на 2 или 3 без остатка, оно составное.
4. Перебирайте потенциальные делители $i$, начиная с 5, с шагом, исключающим кратные 2 и 3 (проверяйте числа вида $6k \pm 1$: 5, 7, 11, 13, 17, 19...).
5. Остановитесь, когда $i^2 > n$.
6. Если ни один делитель не подошел, число простое.

Почему только до $\sqrt{n}$? Если у числа $n$ есть делитель $d$, больший чем $\sqrt{n}$, то обязательно существует парный ему делитель $n/d$, который меньше $\sqrt{n}$. Поэтому достаточно проверить только меньшую половину возможных делителей.

import math

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    # Исключаем четные и кратные 3
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

Метод 2: Решето Эратосфена (для получения списка)

Если вам нужно найти все простые числа в диапазоне (например, от 1 до $N$), метод перебора будет медленным. Используйте «Решето Эратосфена».

Суть метода:

1. Выпишите все числа от 2 до $N$.
2. Возьмите первое незачеркнутое число (сначала это 2) и зачеркните все его кратные (4, 6, 8...), кроме него самого.
3. Перейдите к следующему незачеркнутому числу (3) и зачеркните его кратные (9, 15, 21...; 6 уже зачеркнуто).
4. Повторяйте процесс до $\sqrt{N}$.
5. Оставшиеся незачеркнутыми числа — простые.

Этот алгоритм работает очень быстро для генерации таблиц и имеет сложность $O(N \log \log N)$.

Быстрые признаки исключения составных чисел

Прежде чем запускать сложные вычисления, используйте эти экспресс-проверки, чтобы сразу отсеять заведомо составные числа:

1. Четность: Число оканчивается на 0, 2, 4, 6, 8? Оно делится на 2 (кроме самой двойки).
2. Пятерка: Число оканчивается на 0 или 5? Оно делится на 5 (кроме самой пятерки).
3. Сумма цифр (делимость на 3 и 9): Сложите все цифры числа. Если сумма делится на 3, то и само число делится на 3. Если сумма делится на 9, число делится на 9. Пример: 123 -> $1+2+3=6$. 6 делится на 3, значит, 123 не простое.
4. Окончание: Любое простое число больше 5 оканчивается на 1, 3, 7 или 9. Если число оканчивается иначе, оно составное.

Частые ошибки при проверке

• Считать 1 простым числом. По определению, простые числа должны иметь ровно два различных делителя. У единицы только один делитель.
• Забывать проверять делимость на 2 и 3. Многие начинают перебор сразу с 5 или 7, пропуская очевидные составные числа.
• Использовать полный перебор до $n-1$. Это критически замедляет работу программ даже на современных компьютерах при больших $n$.

FAQ

Является ли число 2 простым? Да, 2 — самое маленькое и единственное четное простое число.

Какое самое большое простое число? Простых чисел бесконечно много (это доказал еще Евклид). Однако наибольшее известное на данный момент простое число является числом Мерсенна ($2^p - 1$) и содержит миллионы цифр. Для практических задач обычно используют числа до $10^{18}$ или специальные большие простые для криптографии.

Подходит ли код на Python для очень больших чисел? Представленный выше код эффективен для чисел до $10^{12}$–$10^{14}$. Для криптографических ключей (сотни цифр) используются вероятностные тесты, такие как тест Миллера-Рабина, которые работают намного быстрее, хотя и дают ответ с определенной вероятностью ошибки (которую можно свести к нулю повторными проверками).