Простые числа и решето Эратосфена

Простые числа и их поиск

Простое число — это натуральное число больше единицы, которое делится без остатка только на единицу и на само себя. Числа 2, 3, 5, 7, 11, 13 — простые. Числа, имеющие другие делители, называют составными: например, 6 делится ещё на 2 и на 3. Единица не относится ни к простым, ни к составным числам. Простые числа — фундамент теории чисел, и задачи на них встречаются в курсе 9 класса.

Проверка одного числа на простоту

Простейший способ — перебрать возможные делители и проверить, есть ли среди них хоть один, кроме единицы и самого числа. Если такой делитель нашёлся, число составное; если нет — простое.

На практике достаточно проверять делители от 2 до квадратного корня из n. Это потому, что у составного числа обязательно есть делитель, не превосходящий его корня. Такая проверка работает гораздо быстрее, чем перебор до самого n.

простое = да

для d от 2 до корень(n):

  если n mod d = 0, то простое = нет

Если после цикла переменная простое осталась равной «да», число простое. Отдельно учитывают, что числа меньше 2 простыми не считаются.

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

Решето Эратосфена — древний и быстрый алгоритм для поиска всех простых чисел до заданной границы N. Его придумал древнегреческий учёный Эратосфен. Идея в том, чтобы выписать все числа подряд, а затем последовательно вычёркивать числа, кратные уже найденным простым. То, что не вычеркнули, и есть простые числа.

1. Выписать все числа от 2 до N.
2. Взять первое невычеркнутое число — это простое.
3. Вычеркнуть все его кратные (числа, делящиеся на него).
4. Перейти к следующему невычеркнутому числу и повторять, пока не дойдём до конца.

Числа 4, 6, 8 уже вычеркнуты как кратные двойке, поэтому при переходе к ним мы их пропускаем. Все числа, оставшиеся невычеркнутыми после завершения, и есть простые. Решето работает заметно быстрее, чем проверка каждого числа по отдельности, поэтому его применяют, когда простых чисел нужно найти много сразу.

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

Кратко о главном

• Простое число делится только на единицу и на само себя.
• Составное число имеет и другие делители; единица — ни то, ни другое.
• При проверке простоты делители перебирают до квадратного корня числа.
• Решето Эратосфена находит все простые числа до границы вычёркиванием кратных.
• Решето быстрее поштучной проверки, когда простых нужно много.