Представьте, что по числовой прямой слева направо катится колесо с длиной окружности, равной 2. На ободе колеса имеется радиальный выступ, которым оно «выталкивает» из числовой прямой каждое второе число.
Затем по числовой прямой катится похожее колесо с длиной окружности, равной 3. Это колесо убирает каждое третье число и т.д.
Все сохранившиеся на числовой прямой числа будут простыми. Можете представить себе ее вид, после того, как по ней проедет n колес с разной длиной окружности? 86.57.146.22616:01, 22 октября 2018 (UTC)[ответить]
А почему 4-ка не вычеркивается? Это ж не простое число.
Updated: А вот теперь все видно :)
UnSigned 20:34, 4 Дек 2004 (UTC)
4-ка вычеркиваеццо! превед медведам
Удаление параграфа внесенного участником Pro100SOm
Поддерживю удаление [1]. Удаленный "алгоритм" попросту неверен - после удаления кратных 2-м и 3-м, числа кратные 5-ти вовсе не будут каждым 5-тым числом среди оставшихся. Решето Ератосфена не удаляет сразу, а метит, и только потом удаляет все составные числа за один проход. Удаляя по одному, превращаем массив в список, и прямая адресация становится невозможной.
Вы видимо описывали постепенный алгоритм, но он вынужден сравнивать значения для их удаления, а это чревато ухудшением алгоритмической сложности (но кстати все-же не на квадрат, а к чуть меньше полуторной степени, в линейном варианте). В любом случае в начальном параграфе нужно описывать базисный, простейший вариант алгоритма. При желании можно будет добавить новую главку в статью. WillNess21:27, 15 октября 2011 (UTC)[ответить]
Изменения марта 2014
Спасибо за ваши исправления. Из новых изменений надо будет взять "историю". Но: безнадежно испорчено главное - описание алгоритма. Пример в статье необходим, чтобы она была понятна - в главном - и детям. Примерам кода в статье не место ("не репозитарий"). Иллюстрация должна быть нормально видна. В уменьшенном виде её было плохо видно.
Вернул часть вашего текста из раздела "история", без повторов других статей Википедии, а именно - статьи о Эратосфене. Эта статья посвящена алгоритму, а к статье о его авторе дается отсылка в предисловии. -- WillNess18:34, 26 марта 2014 (UTC)[ответить]
Внезапно, коллега @Pavel, без объяснения причин, заменил анимацию на менее наглядный вариант. Если в старой анимации простые числа обводятся кружочком, а составные вычёркиваются, то в предложенной, и те, и другие, заливаются цветом. Однако, возможно у старой анимации есть какие-либо другие проблемы? Сергей Леонтьев, Крипто-Про (обс.) 21:22, 11 января 2023 (UTC)[ответить]
Во всей современной литературе методом Эратосфена называют то, что в предисловии статьи пересказано от Хорсли – вычисляя кратные простых чисел, а не то как это описано у Никомаха – вычисляя кратные всех нечётных чисел (т.е. например и кратные 9ти).
То что ниже в статье названо "работой по нечётным числам" это улучшенный вариант Хорсли который вычеркивает нечётные кратные простых чисел из всех нечётных чисел, заранее игнорируя чётные числа. -- WillNess (обс.) 12:31, 28 июля 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)[ответить]
Хорсли ругает эту таблицу как будто в ней все делители для каждого числа находили по отдельности и вписывали их в ячейку этого числа. Но Никомах ведь описывал отсчитывание чисел, так что чтобы получилась эта таблица достаточно было просто использовать сами числа как метки для "вычеркивания" при отсчитывании, так что это он зря. Главное же его озарение было что от уже вычеркнутых чисел отсчитывать не нужно вообще. Но тогда получается что каждый этап обязан быть сделан строго после предыдущих. Никомаху же, как видно, очень нравилась симметрия, когда отсчеты от каждого n по n чисел никак не зависели друг от друга и могли быть произведены в любом порядке (либо вообще параллельно!). -- WillNess (обс.) 01:10, 2 августа 2024 (UTC)[ответить]
"Хорсли ругает эту таблицу как будто в ней все делители..." Это не очень понял, и место Хорсли не нашёл. Можно цитату? Или иное более точное указание.
Кроме того, в статье упоминаются две таблицы. Первая Решето от 3 до 113 "...Aratus published at Oxford in the year 1672, and is adorned with the title of Κόσκινον Ἐρατοσθένης.It contains all the odd numbers from 3 to 113 inclusive, distributed in little cells, all the divisors of every Composite number being placed over it, in its proper cell...". И вторая "...or else, from another comment, translated from a Greek manuscript into Latin, and published in that language, by Camerarius, in which a table of the very fame form occurs, extending from the number 3 to 109 inclusive.", издание которой, я пока не нашел (плохо искал). Но эта таблица другая, несколько меньше, от 3 до 93, включительно, так что её Хорсли, вроде как, ругать не мог.
Что касается Никомаха, то у него написана цель таблицы решета: "отдельно первичные и несоставные числа, отдельно вторичные и составные, и отдельно находятся смешанные". Правда, что есть смешанные хреново описано, предположительно это "третий вид представляется чем-то средним между ними, потому что сам по себе он является вторичным и составным, а по отношению к другому – первичным и несоставным.", т.е. результирующая таблица решета должна содержать делители (достаточно только простых, может квадраты простых: "некоторые измеряются только одной мерой").
