Теорема.

Простых чисел бесконечно много.

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .

Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

Так доказано, что всегда может быть найдено новое простое число, не заключающееся среди любого количества наперед заданных простых чисел. Следовательно, простых чисел бесконечно много.

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

Решето Эратосфена

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

Такой подход к составлению таблицы простых чисел является далеко не идеальным. Так или иначе, он имеет право на существование. Отметим, что при этом способе построения таблицы целых чисел можно использовать признаки делимости , которые немного ускорят процесс поиска делителей.

Существует более удобный способ для составления таблицы простых чисел, называемый . Присутствующее в названии слово «решето» не случайно, так как действия этого метода помогают как бы «просеять» сквозь решето Эратосфена целые числа, большие единицы, чтобы отделить простые от составных.

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .

Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.

Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.

Давайте еще сформулируем и докажем теорему, которая позволит ускорить процесс составления таблицы простых чисел при помощи решета Эратосфена.

Теорема.

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .

Доказательство.

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

Некоторые задания требуют выяснения, является ли данное число простым или составным. В общем случае эта задача далеко не проста, особенно для чисел, запись которых состоит из значительного количества знаков. В большинстве случаев приходится искать какой-либо специфический способ ее решения. Однако мы попробуем дать направление ходу мыслей для несложных случаев.

Несомненно, можно попробовать воспользоваться признаками делимости для доказательства того, что данное число является составным. Если, к примеру, некоторый признак делимости показывает, что данное число делится на некоторое целое положительное число большее единицы, то исходное число является составным.

Пример.

Докажите, что число 898 989 898 989 898 989 составное.

Решение.

Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.

Существенный недостаток такого подхода заключается в том, что признаки делимости не позволяют доказать простоту числа. Поэтому при проверке числа на то, является ли оно простым или составным, нужно действовать иначе.

Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.

Пример.

Число 11 723 простое или составное?

Решение.

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723<40 000 (при необходимости смотрите статью сравнение чисел ). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 <11 723<109 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723

Решето Эратосфена - это старейший из известных способов выписывания простых чисел. В отличие от методов, обсуждавшихся в предыдущих параграфах, он не использует никакой специальной функции. Эратосфен (Erathostenes) был греческим математиком, родившимся около 284 года до н. э. Он владел многими отраслями знаний, однако современники не считали его выдающимся специалистом ни в одной из них. Они прозвали его «Бета» (вторая буква греческого алфавита) и «Пентатлосом». Вот уже 2300 лет мы пользуемся его работами, а полученные им прозвища являются лишним подтверждением величия древнегреческой математики.

«Метод для получения этих [простых чисел] называется по Эратосфену решетом, так как мы берем все нечетные числа, смешанные беспорядочно вместе, и выбрасывая из них, как неким инструментом, или решетом, мы отделяем в первую очередь неразложимые, а во вторую составные посредством их самих.»

Для дальнейшего знакомства с высказыванием Никомаха о решете смотри .

Итак, решето получило свое имя потому, что когда оно применяется к списку натуральных чисел, составные числа просеиваются, а простые задерживаются. Посмотрим, как оно работает.

Прежде всего, цель решета - определить все положительные простые числа, меньшие некоторой верхней границы

которую мы предполагаем целой. Чтобы использовать метод решета, как это делал Эратосфен (имея только карандаш и бумагу), мы поступаем следующим образом. Сначала выписываем все нечетные целые между Причина, по которой мы не трогаем четные числа, заключается в том, что, кроме 2, среди них нет простых чисел.

Теперь мы начинаем просеивать список. Первое число в нем 3. Начиная со следующего числа в списке (это 5), мы вычеркиваем из него каждое третье число. Проделав это до конца, мы вычеркнем все числа из списка, кратные 3 и большие самой тройки.

Теперь выберем наименьшее число из списка, превосходящее 3, которое еще не было вычеркнуто. Таким будет 5, а следующее за ним число - 7. Вычеркиваем каждое пятое число из нашего списка, начиная с 7. Таким образом, все числа, кратные 5, будут вычеркнуты. Продолжаем эту процедуру, пока не дойдем до Заметим, что если мы собираемся вычеркивать каждое число, то всегда надо начинать отсчет с числа даже когда это число было вычеркнуто на предыдущих шагах.

Например, для список нечетных чисел выглядит так:

Вычеркнув каждое третье число начиная с 5, мы получим

Теперь мы вычеркиваем каждое пятое число, начиная с 7, что дает

Мы должны бы теперь вычеркнуть каждое седьмое число, начиная с 9. Но если мы это сделаем, то никакие новые числа

не отсеются. Далее нам нужно бы вычеркнуть каждое одиннадцатое число, начиная с 13, но это опять не даст никакого эффекта. На самом деле, ни одно из чисел, оставшихся в списке после вычеркивания каждого пятого, не будет позже вычеркнуто ни на каком этапе просеивания. Итак, положительные нечетные простые числа, не превосходящие 41, это

В разобранном примере есть пара важных обстоятельств, которые нужно взять на заметку. Во-первых, хотя нам следовало повторять процесс вычеркивания вплоть до граничного числа (41 в нашем примере), мы избавились от всех составных чисел к тому моменту, когда отсеяли кратные 5, и все остальные просеивания оказались излишними. Во-вторых, некоторые числа вычеркивались больше, чем один раз. Такое произошло, например, с 15. Первый раз оно было вычеркнуто, когда мы отсеивали кратные 3. Но 15 также делится на 5, поэтому оно было вычеркнуто снова при отсеивании кратных 5.

Посмотрим, как можно увеличить эффективность решета в свете этих двух замечаний. Начнем со второго из них, т.е. посмотрим, можем ли мы так все организовать, чтобы каждое число вычеркивалось только один раз? К сожалению, ответ на этот вопрос отрицателен: нет хорошего способа добиться этого. Хотя кое-что в указанном направлении сделать все-таки можно.

Предположим, что мы отсеиваем числа, кратные какому-то простому Учитывая наше описание решета, нам следовало бы вычеркивать каждое число, начиная с следующего за числа в списке. Простейшее усовершенствование - это начинать процесс вычеркивания не с а с наименьшего числа, кратного которое не делится на простое число, меньшее Найдем его. Положительные числа, кратные записываются в виде где k - натуральное. Если то делится на число, меньшее а именно на к. Значит, первое

кратное число, которое не делится на простое число, меньшее есть Так что достаточно вычеркивать каждое число, начиная с Однако необходимо обратить внимание на то, что даже после этого нововведения останутся числа, которые будут вычеркиваться не единожды.

Что касается другого замечания, можем ли мы закончить отсев раньше, чем дойдем до шага? На этот раз ответ положителен, он следует того, что мы только что сделали. Допустим, например, что мы вычеркиваем каждое число. Как мы только что видели, первое число, подлежащее вычеркиванию, равно Но если такого числа нет в списке и мы можем забыть о нем. В итоге, нам нужно вычеркивать каждое до тех пор, пока Поскольку целое, это равносильно тому, что В примере, разобранном выше, Вот почему отбрасывание кратных 3 и 5 было достаточно для вылавливания всех составных чисел из списка.

Сейчас мы должны обсудить компьютерную реализацию решета. Список нечетных чисел представляется одномерным массивом, который также принято называть вектором. Напомним, что с каждой ячейкой вектора ассоциируется два числа. Одно из них - значение ячейки, а другое идентифицирует ее местоположение в векторе. Например, в векторе

величина ячейки, отмеченной стрелкой, равна а ее индекс - двум, поскольку она стоит на втором месте в векторе.

Вернемся к решету Эратосфена. Предположим, что мы хотим найти все простые числа, не превосходящие нечетного целого Сначала мы должны построить вектор с ячейками, по одной для каждого нечетного целого Ячейки будут принимать одно из двух возможных значений: 1 или 0. Если значение ячейки равно 0, то нечетное число, ею

представленное, было вычеркнуто на каком-то предыдущем шаге процесса просеивания. Итак, начальное значение каждой ячейки равно 1, поскольку еще нет никаких вычеркнутых чисел. Чтобы «вычеркнуть» число нужно заменить 1, стоящую в ячейке вектора, на 0. Конечно, эта ячейка могла быть «вычеркнута» на предыдущем шаге решета. В этом случае ее значение уже равно 0 и не будет меняться в процессе выполнения следующих шагов алгоритма.

Теперь мы приведем более или менее подробную версию алгоритма для решета Эратосфена, который был описан выше. Она содержит оба усовершенствования, которые мы обсуждали, т.е. каждое число вычеркивается начиная с а алгоритм заканчивается, как только превысит

Решето Эратосфена

Ввод: нечетное натуральное

Вывод: список всех нечетных положительных простых чисел, меньших или равных

Шаг 1. Начинаем с создания вектора ячейками, каждой из которых присвоено значение 1, и полагаем

Шаг 2. Если выписываем все числа для которых значение ячейки вектора равно 1 и останавливаемся; в противном случае переходим к шагу 3.

Шаг 3. Если значение ячейки вектора с номером равно 0, увеличиваем на 2 и возвращаемся к шагу 2; в противном случае переходим к шагу 4.

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

• Научно-популярное

38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена .

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа - и получаем список простых чисел, словно просеяв список через решето.

В виде алгоритма решето Эратосфена формализуется следующим образом:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум - первому простому числу.
3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4, пока возможно.

Очевидно, что компьютерная реализация решета Эратосфена требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил 38-летний перуанский математик Харальд Хельфготт .

Харальд Хельфготт

Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от N до бесконечности Иваном Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что нижняя граница N в работе Виноградова составляет 10 6 846 168 .

Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу, снизив границу N до приемлемого числа 10 29 , а все остальные числа проверили на суперкомпьютере. Его доказательство опубликовано в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао .

Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки - оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена - метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти - следовательно, процесс существенно ускоряется.

«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», - говорит Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.

Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.

Специалисты говорят, что эффективность алгоритма определяется двумя факторами:

1. Количество операций на один бит входных данных.
2. Количество бит в памяти во время выполнения инструкций.

Оптимизация решета Эратосфена

Согласно методу Харди-Литтлвуда, решение задачи задаётся интегралом по единичной окружности от некоторого ряда. Этот интеграл разбивается на два, один из которых оценивается, а про другой доказывается его относительная малость. Составляющие первую сумму называются большими дугами, а вторую - малыми.

Сам математик объясняет метод следующим образом:

«Анализ количества решений производится, по сути, посредством преобразования Фурье . Представьте себе, что простые числа - это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, - это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, - это малые дуги. Весь метод распадается на две части - выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй - на малые».

Образно говоря, вместо 1 гигабайта памяти, т.е. 10 9 байт (не путать с гибибайтом 2 30) нужен всего лишь 1 килобайт (∛10 9 = 10 3 байт).

Гигабайт и килобайт - большая разница, согласитесь.

Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.

Тезисы своей работы Харальд Хельфготт представил на

Переключить меню

В этот статье мы сделаем экскурс в алгоритмы поиска простых чисел и рассмотрим один из алгоритмов, который реализует такой поиск. Этот метод поиска получил название "", в честь древнегреческого математика Эратосфена Киренского. А "решето" потому, что мы как бы просеиваем массив чисел, оставляя в нем только простые числа.

Вспомним, что простым числом , является число, которое без остатка может делиться только само на себя, ну и, конечно же, на единицу. Из школьного курса вы, наверное, помните некоторые из простых чисел - это 5, 7, 11, 13, 17 и так далее. Давайте теперь рассмотрим сам принцип работы алгоритма поиска простых чисел. Этот метод поиска достаточно прост, поэтому, при желании, вам все станет очень скоро понятно.

Решето Эратосфена - алгоритм работы. Язык программирования С++

1. Для примера мы будем производить поиск простых чисел в интервале от 0 до 1000. Для этого нам нужно создать массив логических элементов размерностью 1000. Почему логических, поймете далее. Объявляем массив

Const int size = 1000; bool array;

2. Теперь нам нужно присвоить начальные значения элементам массива, т.к. на данный момент они содержат различный системный "мусор". Поступим так: присвоим всем элементам массива значения "true" - истина или единица. По мере работы алгоритма поиска простых чисел, все элементы массива (они у нас изначально установлены в true) с "простыми" индексами (заметьте, что здесь речь идет именно об индексах, т.к. наши искомые простые числа у нас будут выражаться в значениях индексов элементов массива) останутся быть равными "true", а все остальные установятся в "false" - ложь, или нуль. Т.е. теперь вы поняли, почему массив у нас содержит логические значения, а если и что-то не понятно, то, разобрав код, все встанет на свои места. Заполняем массив, начиная со второй ячейки, т.к. 0 и 1 не относят к простым, а значит и можно сразу их исключить

For(int k = 2; k < size; k++) array[k] = true;

3. А теперь самое важное: рассмотрим сам алгоритм поиска простых чисел, т.е. само решето Эратосфена

Для того чтобы просматривать массив и его индексы нам нужен цикл - делаем цикл (0 и 1 индексы мы не просматриваем). В этом цикле мы будем просматривать значения от 2 до значения корня из size. Почему так? Потому что, дойдя до корня из size, уже будут отсеяны все числа, не относящиеся простым. Поступая таким образом, мы уменьшаем количество итераций, а, соответственно, и нагрузку на процессор компьютера, что есть хорошо.

For(int i = 2; i < sqrt(size); i++) { }

Для "просева" на решете Эратосфена находится первый элемент массива с истинным значением. В самом начале работы программы этим элементом будет элемент с индексом 2. Далее выполняется условие if и мы попадаем на внутренний цикл for, который служит для просмотра остальной части массива (с 3 по 1000 индексы). Значение каждого индекса, а наши числа у нас выражены в индексах, будут проверяться на наличие остатка от деления на 2. Если число делится без остатка, значит, оно уже не может быть простым и значит, соответственно, выставляем эту ячейку в false. Смотрим код

For(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } }

Для более наглядной демонстрации того, что произойдет после первой итерации, где i = 2 привожу рисунок для массива из 20 значений, по аналогии вы поймете, что происходит с нашим массивом из 1000 элементов.

Как видите, все элементы массива со значениями индексов, кратных двум "просеялись" и отметились как false. Это примерно половина значений всего нашего массива.

Переходим на следующую итерацию, в которой i = 3. Выполняется условие if, т.к. 3 не было "просеяно" в предыдущей итерации, попадаем опять же на внутренний цикл, который обрабатывает оставшуюся часть массива (индексы от 4 до 1000).

Рисунок ниже иллюстрирует полученную картину

Как видите, были исключены все числа, кратные трем, не исключенные ранее "двойкой".

Переходим к следующей итерации, где i = 4. Здесь условие if не выполняется, поэтому "просеиваться" ничего не будет. Далее, следующая итерация с i = 5, здесь будут помечены в false значения массива с индексами кратными 5, которые не были помечены ранее по иным критериям: исключаются 25, 35, 45 и так далее. Следующими "рабочими" итерациями, в которых будут выполняться "просевы" являются итерации с i = 7, 11, 13, 17 и так далее, вплоть до корня из size (т.к. после него уже не может встретиться число, не относящееся к простому).

4. Завершающим этапом работы алгоритма "Решето Эратосфена", является печать результатов. Для вывода результатов воспользуемся таким циклом

For(int i = 2; i < mySize; i++) { if(myArray[i] == true) cout << i << endl; }

5. Итог работы:

Алгоритм поиска простых чисел - решето Эратосфена на С++. Первый способ

//прототип функции void printarray(bool, const int); using namespace std; int main() { const int size = 1000; bool array; for(int k = 2; k < size; k++) array[k] = true; for(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } } printarray(array, size); return 0; } //функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; for(int i = 2; i < mySize; i++) { if(myArray[i] == true) { cout << i << endl; counter++; } } //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl; }

Результат работы программы: (было найдено 168 простых чисел)

6. В пятом пункте был изложен первый способ реализации алгоритма поиска простых чисел. Предлагаю вашему вниманию и второй способ, в котором массив будет содержать не логические значения (истина / ложь), а значения целых чисел, которые мы будем "просеивать" на решете Эратосфена. Т.е. принцип работы алгоритма тот же, только реализация несколько иная. Возможно, вам эта реализация понравится даже более предыдущей, смотрим код

Алгоритм поиска простых чисел - решето Эратосфена на С++. Второй способ

//Решето Эратосфена #include void simplePrint(int, const int); using namespace std; int main() { const int size = 100; int array; for(int k = 0; k < size; k++) array[k] = k; array = 0; for(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } } simplePrint(array, size); return 0; } void simplePrint(int array, const int size) { for(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl; }

В этой реализации мы также задаем массиву начальные значения, но уже не логические, а числовые (0, 1, 2, 3, 4, 5 ...). Эти числовые значения и будут теми числами, которые мы будем "просеивать" на решете Эратосфена. Задаем значения таким кодом

For(int k = 0; k < sqrt(size); k++) array[k] = k;

Числа, которые не будут являться простыми, мы будем помечать, как ноль. Мы знаем, что числа 0 и 1 не являются простыми числами, поэтому их сразу можно пометить в нули: первая ячейка массива итак нулевая, а вот вторую, содержащую единицу, нужно поменять

For(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } }

Разберем первую итерацию: i = 2. Выполняется условие if, т.к. вторая ячейка у нас содержит значение 2, и мы переходим во внутренний цикл, который и будет "просеивать" числа. Рассмотрев код, мы видим, что меняются (помечаются) в ноль все значения массива, кратные двум (4, 6, 8, 10, 12 и так далее). В следующей итерации будет то же самое, но уже с шагом 3, помечаются в ноль значения (6, 9, 12, 15, 18 и так далее).

После окончания работы алгоритма поиска простых чисел, выводим значения элементов массива, не равных нулю на экран. Это и будут найденные простые числа

For(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl;

7. При желании, можно как в первой реализации, так и во второй, собрать найденные значения простых чисел в новый массив, который мы создадим динамически. Для этого нужно немного изменить код функции, печатающей результаты работы алгоритма. Вот полученный код

//функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; //подсчитываем количество найденных простых чисел for(int i = 2; i < mySize; i++) if(myArray[i] == true) counter++; //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl << endl; //динамически создаем массив нужного размера int *simple = new int; //заполняем созданный массив простыми числами for(int i = 2, k = 0; i < mySize; i++) if(myArray[i] == true) simple = i; //выводим содержимое на экран for(int i = 0; i < counter; i++) cout << simple[i] << endl; }

Объявляем счетчик counter, который будет считать количество найденных простых чисел. Затем, зная их количество, мы можем динамически создать массив и наполнить его простыми числами. В конце функции выводим его содержимое на экран, тем самым демонстрируя список найденных величин, присутствующих в интервале от 0 до 1000.

Итак, алгоритм поиска простых чисел мы рассмотрели, в частности для этого было использовано "решето Эратосфена". Все вопросы по алгоритму можно задать на форуме, либо в комментариях.

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n , следуя методу Эратосфена, нужно выполнить следующие шаги:

Теперь все не зачеркнутые числа в списке - простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p ). Первое простое число 2 (среди возрастающих положит

Перебор делителей

Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа , тестируя каждое из чисел-кандидатов с помощью перебора делителей .

Псевдокод

Вход : натуральное число n Пусть A - булевый массив, индексируемый числами от 2 до n , изначально заполненный значениями true . для i := 2, 3, 4, ..., пока i ^2 ≤ n : если A [i ] = true : для j := i ^2, i ^2 + i , i ^2 + 2i , ..., пока j ≤ n : если A [j ] = true : A [j ] := false Теперь все числа i , такие что A [i ] = true , являются простыми.

Пример для

Запишем натуральные числа начиная от 2 до 30 в ряд:

Первое число в списке, 2 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 2 2 = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 3 2 = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 5 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 5 2 = 25 ). И т. д.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30