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

В українській програмі прості та складені числа вивчають у 6 класі (п. 4 підручника). просте число має рівно два натуральних дільники: 1 і саме це число. Число 1 не є простим, бо має лише один дільник.

Решето (так називають цей спосіб, його приписують Ератосфену): запиши числа від 1 до 50. Число 1 відклади вбік. Викресли числа, кратні 2 (крім самого числа 2), потім кратні 3, 5 і 7. Числа, які не викреслено, — прості.

Щоб перевірити одне число, не треба ділити його на всі менші числа. Досить спробувати прості числа, квадрат яких не більший за це число.

Якщо жодне з таких простих чисел не ділить це число націло, воно просте. Інакше воно складене число.