Почему решето можно остановить у квадратного корня
Решето Эратосфена устроено не как проверка каждого числа на делимость всеми возможными числами. Оно работает с группами: выбирает очередное простое число и вычёркивает его кратные. Если просеять числа до некоторой границы \(N\), достаточно дойти до простых делителей не больше \(\sqrt{N}\).
Это не просто экономия шагов. Если число до \(N\) составное, его можно представить как произведение двух целых множителей. Не могут оба множителя быть больше \(\sqrt{N}\): тогда их произведение превысило бы саму границу. Значит, у любого составного числа в списке найдётся хотя бы один небольшой делитель — и решето успеет его обнаружить.
Почему вычёркивание начинают с квадрата числа
Допустим, решето дошло до простого числа 5. Его кратные 10, 15 и 20 уже должны быть вычеркнуты: у них есть меньший простой делитель — 2 или 3. Поэтому для каждого простого числа достаточно начинать с его квадрата: у 5 это 25. Все более ранние кратные уже обработаны.
Так каждый составной кандидат исчезает, но одна и та же работа не повторяется без нужды. Числа, которые остались после обработки простых делителей до корня, и есть простые: у них не нашлось делителя, способного вычеркнуть их.
Практический смысл особенно заметен при больших списках: вместо проверки каждого кандидата по отдельности решето многократно отмечает целые последовательности чисел, а верхнюю границу обработки задаёт корень из максимума. Поэтому квадратный корень здесь — не приблизительная уловка, а точный рубеж, после которого новых составных чисел обнаружить уже нельзя.
