Введите натуральное число x. Как найти все простые числа, не превышающие x? Существует метод, называемый сито Эратосфена, история которого восходит к Древней Греции. Шаги сита Эратосфена следующие:
- Напишите список всех целых чисел от 2 до x, оставив только 2. Удалите все кратные 2.
- В оставшемся списке следующее простое число после 2 — это 3. Оставьте 3 и удалите все кратные 3.
- В оставшемся списке следующее простое число после 3 — это 5. Оставьте 5 и удалите все кратные 5.
И так далее. На последнем шаге в оставшемся списке от предыдущего шага оставьте ближайшее простое число, не превышающее x, и удалите все его кратные. Таким образом, оставшийся список будет содержать все простые числа, не превышающие x. Этот метод основан на том факте, что если число a не является простым, то оно обязательно имеет делитель, не превышающий .
Используя сито Эратосфена, можно довольно легко составить таблицу простых чисел. Но что, если нам понадобится быстро определить, является ли не очень большое натуральное число a (например, не превышающее 10 000) простым, а таблицы простых чисел у нас нет? На самом деле, достаточно просто проверить, делится ли a на все простые числа, не превышающие .