Обсуждение:Решето Эратосфена

Представьте, что по числовой прямой слева направо катится колесо с длиной окружности, равной 2. На ободе колеса имеется радиальный выступ, которым оно «выталкивает» из числовой прямой каждое второе число. Затем по числовой прямой катится похожее колесо с длиной окружности, равной 3. Это колесо убирает каждое третье число и т.д. Все сохранившиеся на числовой прямой числа будут простыми. Можете представить себе ее вид, после того, как по ней проедет n колес с разной длиной окружности? 86.57.146.226 16:01, 22 октября 2018 (UTC)

• ... каждое второе число после двух; ... каждое третье число после трех; (каждое четвертое число после четырех уже "вытолкнуто";) ... и т.д. WillNess (обс.) 20:57, 17 сентября 2022 (UTC)

Untitled

А почему 4-ка не вычеркивается? Это ж не простое число. Updated: А вот теперь все видно :) UnSigned 20:34, 4 Дек 2004 (UTC) 4-ка вычеркиваеццо! превед медведам

Зачем убрали модель Сундарама? Она изящна и проста для понимания. Siberex 05:48, 28 июля 2007 (UTC)

Иллюстрация весит 200 кб, может, ее лучше уменьшить или убрать(переместить). --CaesarIII 12:25, 25 мая 2008 (UTC)

Удаление параграфа внесенного участником Pro100SOm

Поддерживю удаление [1]. Удаленный "алгоритм" попросту неверен - после удаления кратных 2-м и 3-м, числа кратные 5-ти вовсе не будут каждым 5-тым числом среди оставшихся. Решето Ератосфена не удаляет сразу, а метит, и только потом удаляет все составные числа за один проход. Удаляя по одному, превращаем массив в список, и прямая адресация становится невозможной.

Вы видимо описывали постепенный алгоритм, но он вынужден сравнивать значения для их удаления, а это чревато ухудшением алгоритмической сложности (но кстати все-же не на квадрат, а к чуть меньше полуторной степени, в линейном варианте). В любом случае в начальном параграфе нужно описывать базисный, простейший вариант алгоритма. При желании можно будет добавить новую главку в статью. WillNess 21:27, 15 октября 2011 (UTC)

Изменения марта 2014

Спасибо за ваши исправления. Из новых изменений надо будет взять "историю". Но: безнадежно испорчено главное - описание алгоритма. Пример в статье необходим, чтобы она была понятна - в главном - и детям. Примерам кода в статье не место ("не репозитарий"). Иллюстрация должна быть нормально видна. В уменьшенном виде её было плохо видно.

Пока что возвращаю прежнюю версию. -- WillNess 18:01, 26 марта 2014 (UTC)

Вернул часть вашего текста из раздела "история", без повторов других статей Википедии, а именно - статьи о Эратосфене. Эта статья посвящена алгоритму, а к статье о его авторе дается отсылка в предисловии. -- WillNess 18:34, 26 марта 2014 (UTC)

Тогда верните еще раздел с модификациями метода. -- Shishkinii 03:52, 27 марта 2014 (UTC)

Примеры реализаций

Считаю, что примеры реализаций должны быть. Они присутствуют практически во всех статьях по алгоритмам (Быстрая сортировка, Сортировка перемешиванием и т.п.). Добавил ссылку на репозиторий http://rosettacode.org/, где можно посмотреть реализацию на других языках. -- Shishkinii 09:25, 27 марта 2014 (UTC)

Не возражаю; главное, сохраните пожалуйста описание алгоритма и псевдокод (и пример тоже). -- WillNess 18:37, 27 марта 2014 (UTC)

Какие есть претензии к старой анимации?

Внезапно, коллега @Pavel, без объяснения причин, заменил анимацию на менее наглядный вариант. Если в старой анимации простые числа обводятся кружочком, а составные вычёркиваются, то в предложенной, и те, и другие, заливаются цветом. Однако, возможно у старой анимации есть какие-либо другие проблемы? Сергей Леонтьев, Крипто-Про (обс.) 21:22, 11 января 2023 (UTC)

Вроде бы нет. Поддерживаю Ваш возврат прежней версии. -- WillNess (обс.) 16:50, 24 февраля 2023 (UTC)