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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая Serge3leo (обсуждение | вклад) в 00:03, 30 июля 2024 (Разъяснение что есть метод Эратосфена). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску

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

Разъяснение что есть метод Эратосфена

Во всей современной литературе методом Эратосфена называют то, что в предисловии статьи пересказано от Хорсли – вычисляя кратные простых чисел, а не то как это описано у Никомаха – вычисляя кратные всех нечётных чисел (т.е. например и кратные 9ти).

То что ниже в статье названо "работой по нечётным числам" это улучшенный вариант Хорсли который вычеркивает нечётные кратные простых чисел из всех нечётных чисел, заранее игнорируя чётные числа. -- WillNess (обс.) 12:31, 28 июля 2024 (UTC)[ответить]

См. также здесь ещё. -- WillNess (обс.) 11:04, 29 июля 2024 (UTC)[ответить]

  • Действительно, Вы правы. Правка была хреновая, чем ОРИС в комментариях плодить, лучше иллюстрацию от авторитетных изданий дать. Оно не только внушительно, но и красиво получается.
  • Опять же, автор алгоритма грек, а у нас не было ни слова по гречески.
  • Но нет, "школьное решето Эратосфена" - это был не Хорсли. В его время, конечно, уже была бумага, а не пергамент, но всё равно. Идея выписать чётные числа, а потом их вычеркнуть без каких-либо бонусов, появилась позже. Но когда, кто и зачем? Я пробовал найти, но не смог.
  • Кстати, может перевод статьи Хорсли в Викитеку занести, я делал черновик перевода, но без вычитки... Да и нужно ли это кому?
  • Относительно, замечания Хорсли "operation very different from it, and far more laborious", то оно нелогично. Эратосфен был практик, не даром же ему приписывают таблицу до 1000, хоть и неавторитетно и без подробностей. Впрочем, Катальди в Trattato de' numeri perfetti (1603), опубликовал таблицу до 750. Если заглянуть в неё, это не только и не столько 132 числа, а гораздо более ценная таблица разложений чисел на множители до 750.
  • Ну, а экономия на отказе от нанесения дополнительных меток для уже помеченных чисел от p до p2 - копеечная (для 750 - 21 шт, для 1000 - 45 шт).
  • Так же, как и опасения Хорсли "Therefore we must have as many marks, or systems of marks, as numbers ; and I do not see, that it would be possible, to find any more compendious marks, than the common numeral characters", без сомнения, теоретически верные, поскольку число простых чисел - бесконечно. Но для случая Катальди (или, возможно, самого Эратосфена), не имеют под собой никаких практических оснований, т.к. до 750 - потребно 8 меток, а до 1000 - достаточно 10 меток.
  • Лично мне очевидно, хотя про то, как именно Катальди оставлял таблицу не известно, но он явно не пользовался интерпретацией Хорсли, а действовал по Никомаху или типа того.
  • Что касается мысли Хорсли, что Эратосфен отличный математик и должен же был это видеть, то да, согласен, наверняка видел. Но, полагаю не придавал значения и не считал целесообразным просто вычеркивать числа и изводить пергамент. Таким образом, вероятно, именно Хорсли следует считать автором вариации метода: начинать вычёркивать не с 3*p, а с p2 Сергей Леонтьев, Крипто-Про (обс.) 23:52, 29 июля 2024 (UTC)[ответить]