Теория
Генератор простых чисел выписывает все простые числа, не превосходящие заданную границу. Прямой перебор «для каждого числа проверять все делители» слишком медлителен; классическое решение — решето Эратосфена.
В решете выписывают числа от 2 до \(N\), берут первое незачёркнутое — это 2, простое — и вычёркивают все числа, кратные ему. Затем берут следующее незачёркнутое (3), вычёркивают его кратные и так далее. Уже к числу \(\sqrt{N}\) процесс останавливается: все оставшиеся незачёркнутыми числа простые.
Важно: при вычёркивании кратных можно начинать с квадрата простого числа — все меньшие кратные уже вычеркнуты предыдущими шагами.
Пример с решением
- Условие. Выпишите все простые числа до 20.
- Формула. Решето Эратосфена: последовательно вычёркиваем кратные найденных простых.
- Подстановка. Ряд: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.
- Вычисление. Оставляем 2, вычёркиваем 4, 6, 8, …; оставляем 3, вычёркиваем 9, 15, …; после числа 5 вычёркивать больше нечего — \(\sqrt{20} \approx 4{,}47\).
- Ответ. Простые до 20: 2, 3, 5, 7, 11, 13, 17, 19. Калькулятор с границей 20 выдаст ровно эти восемь чисел.
Главное
- Решето Эратосфена — вычёркивание кратных найденных простых.
- Останавливаемся на простых, не превосходящих \(\sqrt{N}\).
- Первые простые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.