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

Определения и обозначения

Простое число — натуральное число, большее 1, которое делится без остатка только на 1 и на само себя. Например, у числа 13 делители 1 и 13. Это определение позволяет отличать простые числа от остальных и составлять их список.

Составное число — натуральное число, большее 1, имеющее делители, кроме 1 и самого числа. Например, 12 делится на 2, 3, 4 и 6, поэтому оно составное. Понимание этого термина помогает объяснить, какие числа нужно вычёркивать из таблицы.

Делитель числа — натуральное число, на которое данное число делится без остатка. Например, 3 является делителем 18, потому что 18 : 3 = 6. Поиск делителей нужен, чтобы установить, является число простым или составным.

Таблица простых чисел — список простых чисел, полученный последовательным исключением составных чисел. В ней сначала записывают все числа выбранного промежутка, а затем вычёркивают кратные уже найденных простых чисел. Такой список ускоряет проверку чисел и поиск простых множителей.

Как это устроено

Число 1 не относят ни к простым, ни к составным, потому что у него только один натуральный делитель — 1. Для простого числа нужны ровно два различных делителя: единица и само число. Составное число, наоборот, имеет хотя бы один дополнительный делитель.

Чтобы начать составлять таблицу, выписывают все натуральные числа от 2 до выбранной границы. Первое число 2 оставляют, потому что оно не делится на меньшие числа, кроме 1. Затем его кратные 4, 6, 8 и так далее можно исключить: каждое из них точно имеет делитель 2.

После выбора очередного простого числа p вычёркивают его кратные, большие самого p. Это числа 2p, 3p, 4p и другие, поэтому каждое из них имеет делитель p и не может быть простым. Само число p оставляют, ведь оно и должно попасть в таблицу.

Для ускорения кратные p начинают вычёркивать с p², а не с 2p. Например, у числа 5 кратные 10, 15 и 20 уже были вычеркнуты при обработке 2 и 3. Первое новое кратное — 25, а все меньшие кратные 5 имеют другой меньший простой делитель и исключены раньше.

При составлении таблицы до N достаточно обрабатывать простые числа, не превосходящие √N. У любого составного числа есть делитель, не больший его квадратного корня: если бы оба множителя были больше √N, их произведение превысило бы N. Поэтому при отсутствии делителей среди простых чисел до √N число N является простым.

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

Чтобы пользоваться таблицей, найдите нужный диапазон и просмотрите его второй столбец. Если числа там нет, оно либо составное, либо находится за пределами указанного промежутка. Например, 67 есть в строке 61–70, а 68 в списке отсутствует.

Разбор задач

Задача 1

Условие: определите, какие из чисел 1, 2, 9, 13 и 21 являются простыми. Сначала нужно исключить число 1, поскольку оно не подходит по определению. Для остальных чисел проверим наличие делителей, кроме 1 и самого числа.

1. Число 2 делится только на 1 и 2, поэтому оно простое.
2. Число 9 делится на 3, значит, у него есть дополнительный делитель и оно составное.
3. Число 13 не делится на 2 и 3; других простых делителей до √13 меньше 13 нет, поэтому оно простое.
4. Число 21 делится на 3 и 7, поэтому оно составное.

Ответ: простые числа — 2 и 13; 1 не является ни простым, ни составным, а 9 и 21 — составные.

Задача 2

Условие: составьте таблицу простых чисел от 2 до 30 способом последовательного вычёркивания кратных. Важно не вычёркивать выбранное простое число. Последовательно рассматриваем невычеркнутые числа.

1. Оставляем 2 и вычёркиваем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 и 28.
2. Следующее невычеркнутое число 3 оставляем и вычёркиваем его новые кратные 9, 15, 21 и 27.
3. Следующее число 5 оставляем и вычёркиваем 25; его меньшие кратные уже исключены.
4. Число 7 тоже оставляем, но новые кратные до 30 отсутствуют, так как 7² больше 30.

Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.

Задача 3

Условие: проверьте, является ли 97 простым числом, используя таблицу простых чисел до 10. Находим √97: это примерно 9,8, поэтому достаточно проверить простые числа 2, 3, 5 и 7.

1. 97 не делится на 2, потому что оно нечётное.
2. Сумма цифр 9 + 7 = 16, поэтому на 3 число не делится.
3. Последняя цифра не равна 0 или 5, значит, 97 не делится на 5.
4. При делении 97 на 7 получается остаток 6, поэтому делимость на 7 также отсутствует.

Ответ: 97 — простое число, потому что ни один простой делитель, не превосходящий √97, его не делит.

Типичные ошибки

Ошибка: считать 1 простым числом. Так делают, потому что 1 делится на себя и кажется похожим на простое число. Проверьте число делителей: у простого их два, а у 1 только один.

Ошибка: вычёркивать выбранное простое число вместе с его кратными. Причина — смешение самого числа p с числами 2p, 3p и далее. Оставляйте p в таблице и удаляйте только большие числа, кратные ему.

Ошибка: начинать вычёркивание с 2p, не объясняя повторную работу. Такое действие не меняет результат, но заставляет снова проверять числа, уже исключённые раньше. Для быстрого способа начинайте с p² и убедитесь, что меньшие кратные уже вычеркнуты.

Ошибка: проверять делимость числа на все числа до него. Это лишняя работа, поскольку достаточно простых делителей до √N. Сначала найдите квадратный корень числа, затем проверяйте делимость только на простые числа до этой границы.

Связь с другими темами

До изучения таблицы нужны натуральные числа, деление с остатком и понятие делителя. Эти знания помогают распознавать делимость и объяснять, почему число является простым или составным.

Таблица простых чисел используется при поиске простых делителей и разложении натуральных чисел на простые множители. Например, с её помощью легче разложить 60 как 2 · 2 · 3 · 5.

Понятие простого числа понадобится при изучении делимости, наибольшего общего делителя и наименьшего общего кратного. Простые множители позволяют сравнивать строение чисел и выполнять вычисления по понятным правилам.

Что запомнить

• Простое число имеет ровно два натуральных делителя.
• Составное число больше 1 и имеет более двух натуральных делителей.
• Число 1 не является ни простым, ни составным.
• Число 2 — единственное чётное простое число.
• При составлении таблицы вычёркивают кратные уже найденных простых чисел.
• Чтобы проверить число N на простоту, достаточно проверить его делимость на простые числа до √N.