Решето для простых чисел

В российской программе простые и составные числа изучают в 5 классе вместе с признаками делимости. простое число имеет ровно два натуральных делителя: 1 и само это число. Число 1 не является простым, потому что у него только один делитель.

Решето (так называют этот способ, его приписывают Эратосфену): запиши числа от 1 до 50. Число 1 отложи в сторону. Вычеркни числа, кратные 2 (кроме самого числа 2), потом кратные 3, 5 и 7. Числа, которые не вычеркнуты, — простые.

Чтобы проверить одно число, не нужно делить его на все меньшие числа. Достаточно попробовать простые числа, квадрат которых не больше этого числа.

Если ни одно из таких простых чисел не делит это число нацело, оно простое. Иначе оно составное число.