Доброго времени суток, товарищи! Сегодня речь пойдет в продолжение предыдущей темы, а именно, мы будем писать Решето Эратосфена за линию.
Те, кто не знаком с оригинальным решетом - сюды.
Основная проблема Эратосфена в том, что мы помечаем составные числа по несколько раз, наша задача состоит в том, чтобы как-то помечать числа только по разу.
Предположим, что мы знаем минимальный простой делитель какого-то произвольного числа, k - p[k]. и, если мы будем домножать k на простые числа до p[k] (p[j]), то мы однозначно получим число, у которого наименьший простой делитель p[j]. Почему? Просто потому, что при разложении полученного числа на множители мы получим следующую картину: x = p[j]*k, где у k наименьший простой делитель >= p[j] (потому что мы так домножали), а у p[j] наименьший простой делитель само же число. Отсюда мы однозначно получаем число, у которого наименьший простой делитель p[j].
Теперь поймем почему же мы не встретим это число еще раз при умножении. Пойдем от противного. Тут следует добавить, что если бы мы встретили еще раз это число, то простое число, на которое мы бы домножали какое-то произвольное k, точно бы не было то самое, минимальное, потому что разложение вида x=p[j]*k, где p[j] - простое, единственно (k - отлично от того случая, когда мы домножали на простое минимальное). Следовательно p[j] было бы не минимальным простым делителем, но по вышесказанному оно будет минимальным простым, противоречие, значит еще раз попасть в уже помеченное число мы не можем. Ч.т.д.
Так как мы побываем в каждом числе по разу, то алгоритмическая сложность O(n).
По сути, на практике отличие от оригинального Эратосфена будет примерно в два раза, а оптимизированные версии Эратосфена и вовсе будут примерно одинаковы по скорости (о них я рассказывал в предыдущей статье). Практически не выигрывая в скорости, мы сильно проигрываем в памяти (нам придется хранить массив не тольно именно чисел, о реализации пойдет речь дальше, но и отдельно массив простых чисел. Но кроме нахождения простых чисел, этот алгоритм практически вычисляет факторизацию чисел от 1 до n, что несомненно является огромным плюсом алгоритму.
В массиве all мы будем хранить наименьшие простые делители, а в массиве pr - все найденные в отрезке простые числа. Если мы попали в ячейку all с 0, значит мы там еще ни разу не были, значит число будет простым, а у простого числа наименьший простой делитель - само число. Дальше в независимости от того простое сейчас или нет рассматривается число, мы домножаем это число на все простые числа, которые меньше наименьшего простого делителя числа и пишем туда их наименьший простой делитель (более подробно об этом выше). Ответ будет лежать в массиве простых чисел - pr.
Всем спасибо за внимание! Надеюсь встретиться с вами в следующих статьях!