Как найти все простые числа на отрезке

Об античном ученом Эратосфене Киренском, которому приписывают наш метод, википедия говорит следующее [1]:

«Эратосфен Киренский (др.-греч. ἘρατοσθένηςὁΚυρηναῖος; 276 годдон. э.—194 годдон. э.) —греческий математик, астроном, географ, филолог и поэт. Ученик Каллимаха, с 235 г. дон. э. —глава Александрийской библиотеки. Первый известный учёный, вычисливший размеры Земли.»

Обычно метод Эратосфена описывают при помощи картинки, где изображено некоторое количество первых чисел натурального ряда (единицу, как и договорились, мы сразу выбросим из рассмотрения):

Идея в том, что мы берем подряд числа из натурального ряда. Для каждого взятого числа k добавляем это же число k и полученный результат вычеркиваем. Потом снова добавляем и снова вычеркиваем. Делаем так, пока не дойдем до конца интервала. Почему мы вычеркиваем эти числа? Потому что это каждое такое число кратно k, оно заведомо составное, а не простое.

Возьмем для начала двойку. Кстати, а саму двойку надо вычеркивать или нет? Ответ, с одной стороны, очевидный, с другой стороны – какой-то неожиданный. Этот ответ звучит так: если очередное  число  при проходе по натуральному ряду  еще не вычеркнуто, то и не надо его вычеркивать, оно «хорошее». Это как в сказке «Волшебная лампа Алладина» султан в сердцах постановил для своей непослушной дочери: «Отдам тебя замуж за первого встречного!». Вот мы начали перебирать наш ряд, взяли двойку. Мы ее встретили в первый раз, она еще не вычеркнута – значит, подходит! Это простое число – и мы его не вычеркиваем.

Но мы идем дальше. К двойке прибавляем само это число 2+2. Получилось 4. Надо ли здесь задавать себе вопрос: в первый раз или не в первый мы встретили это число? Нет, не надо. Потому что мы работаем с двойкой! Получившееся число 4 вычеркиваем.

Кстати, как долго нам надо идти вперед? Это зависит от точной постановки задачи, а мы пока этого не сделали, и подходили к задаче по-простецки – находили простые числа. Но мы не уточняли, сколько именно простых чисел мы хотим найти. В самом деле – сколько?

Поиск простых чисел на заданном интервале

Наверное, имеет смысл искать N первых простых чисел. Но это не очень простая постановка задачи  – вы это скоро увидите. Давайте для начала рассмотрим более простую задачу: найти все простые числа, меньше или равные заданного числа M.

Пусть это M равно 50. Значит,  надо добавлять нашу двойку, пока не дойдем до 50.

Начав с 2, и добавляя по 2, мы получим следующую картину (красным выделены вычеркнутые числа):

Теперь давайте разбираться с числом 3. Саму тройку мы оставляем по принципу «первого встречного», а дальше зачеркиваем 6, 9, 12, и так далее:

Нетрудно видеть, что какие-то числа нам пришлось вычеркивать по второму разу, начиная с той же шестерки – ведь мы уже вычеркнули 6, когда работали с числом 2. Есть ли в этом что-то нехорошее? Если рассматривать эту работу с вычислительной точки зрения, то как будто бы это нехорошо. Вообще  любая повторная работа, которую можно избежать – это нехорошо. Потому что мы тратим вычислительное время. Но в данном случае лучше все же закрыть глаза на эту избыточность. Потому что иначе нам пришлось бы как-то проверять, а не вычеркивали ли мы это число раньше?  А это, само по себе, тоже лишняя вычислительная работа.

С числом 3 разобрались. Надо ли нам разбираться с числом 4? Нет, принцип «первого встречного» говорит, что не надо – четверку мы уже встречали раньше, когда вычеркивали, начиная с  двойки.

Тогда идем дальше и смотрим на число 5. Пятерка – как раз «первый встречный», мы еще ее «не видели». Значит, оставляем 5 в «хороших числах», а вот 10, 15, 20, 25 и так далее до 50 (включительно) – вычеркиваем:

Число 6 снова пропускаем, зато семерка – «первый встречный», и мы вычеркиваем 21 (14 уже вычеркнули), 28, 35, 42, 49:

Как долго следует продолжать этот процесс? В самом начале мы сказали, что надо перебирать все числа в заданном интервале [2; M]. Но нетрудно догадаться, что на самом деле достаточно остановиться на числе M/2 (или его целой части для нечетных M). Ведь когда мы перейдем к следующему за ним числу K = [M/2] + 1, то число K + K заведомо окажется вне диапазона  [2; M].

В любом случае, когда мы закончим перебирать все числа в интервале [2; M]  (или только первую половину этого интервала), мы получим, что больше нам вычеркивать нечего. Это значит, что числа, оставшиеся незакчеркнуыми – и есть простые:

Всего мы нашли 16 простых чисел на нашем интервале, причем заранее мы не могли знать, сколько именно мы найдем. В этом и состоит главная прелесть и загадка простых чисел: не существует простого понимания того, насколько плотно простые числа расположены на числовой оси. Вспомним, какую постановку задачи мы сами для себя выбрали – найти все простые числа на заданном отрезке,  – то есть, не превосходящие некоторого числа M.

Это, конечно, здорово, но согласитесь – куда интереснее решить задачу о нахождении конкретного количества N простых чисел. На самом деле, с точки зрения некоторого вымышленного, но типового «заказчика», куда как важнее получить конкретное количество первых простых чисел, чем просто все, что можно найти на заданном интервале.

Давайте для начала запрограммируем на Python первую задачу – для заданного интервала, а потом станем думать, как это трансформировать в решение второй задачи.

# указываем верхнюю границу поиска

maxNum = 100

# создаем список вообще всех целых чисел от 0 до maxNum включительно

nums = list(range(maxNum + 1))

# мы будем рассматривать ненулевые числа; единицу тоже занулим сразу,

# потому что мы договорились, что это число не является простым

nums[1] = 0

# сюда будем складывать «женихов» – «первых встречных», т.е. найденные

# простые числа

primes = []

# внешний цикл – проход по заданному интервалу

for i in nums :

    # рассматриваем только ненулевые числа; 0 – значит число негодное,

    # мы его вычеркнули (не «первый встречный») 

    if i > 1:

        # Внутренний цикл: для каждого числа i проходим «прыжками» с шагом i       

        for j in range(i + i, len(nums), i):

            nums[j] = 0

        # не забываем сохранить само число

        primes.append(i)

print(len(primes))

В результате чего убедимся, что на отрезке [1; 100] всего 25 простых чисел. А теперь представим, что нашему заказчику совершенно все равно, какой интервал мы рассматриваем. Ему важно, чтобы мы нашли ему 100 первых простых чисел. А уж на каком интервале они лежат – как получится. Как нам нужно действовать?

Поиск заданного количества простых чисел

Наверно, самый простой ответ будет такой: давайте возьмем поисковый интервал «на глазок». Можно предположить, что это должен быть достаточно большой интервал. Например, выше мы убедились, безо всякого программирования, что на отрезке [1; 50] есть 16 простых чисел. Значит, если наш заказчик  хочет найти  100 простых чисел, можно взять поисковый интервал примерно от 1 до 300.

Почему бы и нет. Но на самом деле, частота, с которой на числовой оси встречаются простые числа, убывает с ростом максимального номера простого числа. Или, другими словами, необходимый поисковый интервал растет быстрее (это называется «нелинейно»), чем количество простых чисел, расположенных на этом интервале.

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

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

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

Как же нам поступить? Предыдущее решение было слишком ненадежным, мы это уже поняли. Следующее предложение: давайте постепенно наращивать поисковый интервал. Скажем, мы обработали интервал [1; 50], нашли 16 простых чисел, а заказчику надо 100 – значит, у нас явно «недолет». Давайте искать заново, скажем, на удвоенном интервале [1; 100] (двойка – это хороший коэффициент, поверьте). Если снова найдем меньше чисел, чем надо – еще раз удвоим: будем искать на отрезке [1:200], и так далее. Пока не найдем столько простых чисел, сколько у нас просят. А если найдем больше, чем нужно – это не беда: больше – не меньше, лишние всегда можно отбросить.

В каком-то смысле, на этом месте можно было бы остановиться и считать задачу решенной. Мы нашли  принципиальный способ находить требуемое количество первых простых чисел. Но, к сожалению, с практической точки зрения,  этот способ очень плохой. Все дело в том, что нам придется многократно повторять одну и ту же работу. Представьте, что мы уже проделали все нужные вычисления на отрезке [1; M] и не нашли требуемое количество N простых чисел. Мы говорим: не беда! – и начинаем работу заново на отрезке [1; 2M]. И нам неизбежно придется пройти сначала по отрезку [1; M], но ведь мы это уже делали! Получается, мы сделаем эту работу повторно.

И это совсем не безобидная избыточность. Попробуем как-то оценить объем вычислительной работы. Пусть на начальном интервале [1: M] мы проделали условно m вычислительных операций. Сколько операций мы выполним при расширении поискового интервала? Давайте для оценки считать, что проработка любого интервала длины M требует одно и то же – m – количество вычислений. На самом деле это не так – выше мы уже поняли, что «чем дальше в лес», тем реже простые числа. Но у нас нет на руках никакого точного «закона», который говорил бы – насколько реже. Значит, нам ничего не остается, как довольствоваться той гипотезой, что у нас есть – пусть число вычислений на интервале длиной М всегда равняется m. На самом деле, мы таким образом завысим нашу оценку. Но с чего-то надо начать.

Вообще, такие оценки далеко не всегда легко выполнять, но программист постепенно должен этому учиться. Кроме этого, как и почти все в программировании, такие оценки можно делать по-разному. Конечно – при правильно проведенной оценке конечный результат не должен изменяться. Поэтому автор сделает так, как нравится ему. Изобразим наши поисковые интервалы геометрически:

Мы видим казалось бы – простую вещь: при увеличении поискового интервала в 2 раза объем вычислений увеличился в 2 раза. Однако – не совсем так. Ведь мы уже один раз проделали кусок работы на начальном интервале [1; M], а потом мы еще дважды ее выполнили. Всего получается уже
m + 2m = 3m.

Пусть нам снова не хватило простых чисел, найденных на интервале [1; 2M]. Тогда мы переходим к интервалу [1; 4M]. И мы видим, что полное количество проделанных нами вычислений от самого начала работы равно m + 2m +4m = 7m.

Теперь мы уже можем разглядеть, по какому закону нарастает объем вычислений – это закон геометрической прогрессии. Поскольку знаменатель этой прогрессии равен 2, сумма k членов прогрессии равна m * (2^k – 1) / (2 -1), то есть – m * (2^k – 1). Напомним: k слагаемых в нашей сумме означает, что мы k-1 раз удваивали размер поискового интервала.

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

Нам снова поможет довольно простая идея: давайте, вместо того, чтобы все время начинать работу заново, попробуем просто продолжать эту работу. Легко сказать, а как сделать?

Если бы мы проверяли только деление, скажем на 2 или 3, или любое другое, но одно конкретное число,  мы бы шли и шли вдоль первого интервала, потом увидели бы, что одного этого интервала нам не хватае, и пошли бы дальше, и нет проблем. Но проблема в том, что проработав число 2, мы его бросаем, и работаем с числом 3, и так далее. А когда приходит время расширить интервал – мы уже ничего не помним, и поэтому не знаем, за что хвататься.

Какое число не возьми – ту же двойку – мы не знаем, откуда надо начинать новый отсчет.

Хорошая формулировка проблемы часто содержит, частично или даже полностью,  путь к ее решению, и это именно наш случай. Если мы не знаем, откуда нам начинать прыгать через 2 (3, 5, 7 – и так далее) – давайте просто будем это записывать, чтобы не забыть.

Запоминать лучше в виде словаря. Словарь – это простейший объект в языках Python и JavaScript. Возможно, и в каких-то других языках тоже, но кругозор автора не бесконечен. А в этих двух языках словарь представляет собой перечень пар <ключ> : <значение>, заключенный в фигурные скобки {}:

{

            <ключ_1> : <значение_1>,

<ключ_2> : <значение_2>,

<ключ_3> : <значение_3>,

…

}

В качестве ключа могут применяться разные типы данных, но мы для простоты будем считать, что у нас ключами будут числа (чаще всего применяют строки). Значение может быть вообще любое: число, строка, список, или любой другой объект (не обязательно словарь – есть еще экземпляры классов, но мы в эту область не заглядываем).

В языках Си и С++ существует похожий тип данных, называемый структурой (struct), но это менее гибкий тип данных, чем словарь Python. Любопытно, что в JavaScript вообще все объекты, включая очень сложные, строятся на основе словарей, а классов, как в С++, Java или Python, нет вообще, но можно наследовать объекты. В этом отношении, JavaScript – самый необычный объектно-ориентированный язык.

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

Что именно нам надо запоминать? Во-первых, необходимо запоминать сами простые числа – все, что мы нашли к текущему моменту. Во-вторых, для каждого такого числа надо запоминать – внимание! – последнее число, которое мы вычеркнули, удаляя числа «по поводу» этого простого числа.

Возможно, это не самая простая и понятная формулировка, поэтому давайте повторим ее другими словами. Допустим, мы нашли простое число 2. Мы последовательно вычеркивали, в нашем текущем интервале, числа: 4, 6, 8, … и остановились, например, на числе 240. А наш интервал поиска заканчивался, например, на числе 241. Дальше нам идти некуда – в рамках данного интервала.

Но ведь далее мы расширим наш интервал и пойдем дальше. Для этого мы должны знать, что в предудыщий раз мы остановились на числе 240. Остановились, потому что число 240+2=242 лежало уже вне прошлого интервала. Но оно уже лежит в новом интервале. Начиная с этого числа, можно продолжать работу. Поэтому число 240 надо запомнить, и его надо запомнить «по поводу» простого числа 2.

Запоминать эту пару чисел мы будем в виде одной записи в словаре:

{

2 : 240,

…

}

            Назовем наш словарь pev_primes от слов “previous primes” – «предыдущие простые». Это название отражает тот факт, что, приступая к работе с новым интервалом, у нас уже есть запас информации, наработанный на предыдущих интервалах. На самом деле, здесь будут не только «предыдущие» числа,  ведь мы будем оперативно добавлять сюда только что найденные простые числа. Но, все-таки, это название напомнит нам, что мы работаем с накопленными данными.

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

            Дополним наш предыдущий код заполнением словаря pev_primes по мере того, как мы проходим по начальному поисковому диапазону [1; maxNum]:

maxNum = 100

nums = list(range(maxNum + 1))

nums[1] = 0

prev_primes = {}

# внешний цикл – проход по заданному интервалу

for i in nums :

    if i > 1:

        # Внутренний цикл: для каждого числа i проходим «прыжками» с шагом i

        for j in range(i + i, len(nums), i):

            nums[j] = 0

Последнее значение j и есть то число, последнее для i, которое мы вычеркнули в текущем интервале, поэтому его надо запомнить.

        prev_primes[i] = j

          Давайте посмотрим, что мы сохранили:

print(prev_primes)

Это только первый вопрос, но есть еще и другой: почему значение 94 у ключа 53 такое же, как у ключа 47. Есть и третий вопрос: почему значение 94 так и повторяется до самого конца словаря pev_primes.

Обнаружить причину произошедшего на самом деле несложно. Число 53 – первое, большее половины нашего диапазона. Если мы добавим 53 к 53, мы сразу выходим за пределы поискового диапазона. Это значит, что цикл

 for j in range(i + i, len(nums), i):

– даже не начнет выполняться. Тогда, что же мы будем записывать в наш словарь в инструкции prev_primes[i] = j ? Это будет то значение j, которое осталось от предыдущего i, при котором цикл for еще выполнялся – как раз 94.

Значит, нужно ввести какую-то проверку, что цикл for вообще выполняется, что поток исполнения заходит «внутрь» тела цикла. Давайте сделаем это «по-питонски»: создадим сразу список на удаление, и тогда увидим – пустой он или нет.

for i in nums :

    if i > 1:  

        to_remove = range(i + i, len(nums)+1,

        for j in to_remove :

            nums[j] = 0

        if len(to_remove) > 0:

            prev_primes[i] = j

print(prev_primes)

            Теперь все хорошо, нет «паразитных» записей в нашем словаре. Настал момент научиться использовать накопленные данные при расширении поискового диапазона. Давайте оформим эту работу в виде функции, которой мы будем передавать в качестве аргументов границы очередного поискового диапазона (минимальное minNum и максимальное число maxNum в этом диапазоне), а также имеющийся на данный момент словарь найденных простых чисел prev_primes :

def add_primes(minNum, maxNum, prev_primes) :

# создаем список, отображающий новый поисковый интервал

nums = list(range(minNum, maxNum+1))

          # получаем сразу - в виде кортежа (prime, last_removed)

          # - простое число и его «последнее удаленное»

          for prime, last_removed in prev_primes.items():

          Cписок на удаление создается чуть более хитро, чем ранее: мы добавляем к «последнему удаленному» его ключ – простое число. Ведь последнее удаленное было в предыдущем интервале, а следующее за ним уже не помещалось в тот интервал, но зато оно как раз попадает в новый (текущий) поисковый интервал. С него и начнем удалять:

          to_remove = range(last_removed  + prime, maxNum+1, prime)

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

#def add_primes(minNum, maxNum, prev_primes) :

#        …

          # for prime, last_removed in prev_primes.items():

# …

          for num in to_remove :

nums[num - minNum] = 0

Снова запоминаем «последнее удаленное» число, а это ни что иное, как последний элемент в списке на удаление:

#def add_primes(minNum, maxNum, prev_primes) :

#        …

          # for prime, last_removed in prev_primes.items():

# …

prev_primes[prime] = to_remove[-1]

Итак, что мы сделали. Мы продолжили вычеркивание чисел, кратным тем простым, которые мы нашли на предыдущем интервале, точнее – на всех предыдущих интервалах. Мы же будем продолжать расширять поисковый интервал неопределенно долго. Но на текущем интервале должны найтись какие-то новые простые числа в списке nums!

def add_primes(minNum, maxNum, prev_primes) :

nums = list(range(minNum, maxNum+1))

…

# ищем новые простые

for num in nums :

            if num != 0:    

Первое же встречное, но обязательно ненулевое – т.е. не вычеркнутое число, и есть простое, как и раньше.

                        next_prime = num

Как и раньше, удалять надо с числа next_prime + next_prime, с шагом next_prime.

                         to_remove = range(next_prime * 2, maxNum+1, next_prime)

            for num1 in to_remove:

                  nums[num1 - minNum] = 0

Как и раньше, к данному простому числу next_prime привязываем то число, которое мы вычеркнули последним:

                            if len(to_remove) > 0:

                    prev_primes[next_prime] = to_remove[-1]

Наша главная функция готова, но нам надо написать функцию-обертку, которая будет многократно вызывать функцию add_primes(). Нужно найти n первых простых чисел.  Но важно понимать, что мы не сможем сразу найти в точности n чисел, потому что мы заранее не знаем, как меняется частота простых чисел на числовой оси, и мы об этом уже говорили. У нас неверняка будет «перелет», т.е. мы найдем не менее n чисел, но это тоже вовсе не плохо.

#Находит не менее первых n простых чисел

def get_n_primes(n):

#начальный поисковый диапазон – от 2 до 2*n

          minNum = 2

     maxNum = 2*n

     prev_primes = {}

# будем считать, сколько раз мы раздвигаем начальный интервал

cnt = 0

          while len(prev_primes) < n:

            cnt += 1

            print(cnt)               

# ключи словаря и есть те простые числа, что мы нашли

# на данный момент

                    print(list(prev_primes.keys()))

            add_primes(minNum, maxNum, prev_primes)

                    # расширяем интервал: добавляем справа такой же по длине

                    minNum = maxNum + 1

            maxNum *= 2

          return list(prev_primes.keys())

Наконец, выполняем все вместе:

a = get_n_prime(100)

Выше уже говорилось, что  мы не можем так подгадать, чтобы найти ровно требуемое (например, 100) количество простых чисел. Но мы можем проверить, что нашли не меньше, и в этом месте прекращаем развдигать наше раздвижное сито. И, чтобы вывести ровно 100 чисел, просто возьмем срез от найденного списка:

a = a[:100]

print(a)

Однако, эта программа почему-то «зависает»: мы увидим, что счетчик итераций cnt безостановочно увеличивается, а список найденных простых чисел не растет:

…

14

[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]

15

[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]

16

[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]

Мы видим нечто такое, на что вовсе не расчитывали: набор простых чисел перестал расти. Как понять – что мы делаем не так? Добавим отладочную печать в том месте, где мы пополняем наше хранилище. Будем выводить найденное простое число и то «последнее вычеркнутое», которое с ним связано.

    for num in nums :

        if num != 0:

            …

            next_prime = num

            print(next_prime, end=' : ')  

…

            if len(to_remove) > 0:

                print(to_remove[-1], end='n')

                prev_primes[next_prime] = to_remove[-1]

Получаем такую трассировку нашей программы:

…

2 : 200

3 : 198

…

89 : 178

97 : 194

101 : 103 : 107 : 109 : 113 : …

Итак, что происходит? Новые простые числа – появляются, но мы ничего не записываем «по этому поводу». Почему? Есть только одна возможность: не выполняется условие if len(to_remove) > 0, то есть – список to_remove попросту пустой, но почему? Сразу сообщим правильную догадку (к ней, в самом деле, несложно прийти): next_prime * 2 (он же next_prime + next_prime) в какой-то момент оказывается больше maxNum, и список (точнее, итератор) to_remove оказывается пустым. Список пустой – значит, ничего и не вычеркиваем, работа дальше не идет. 

Точнее говоря – работа идет, но недостаточная: мы вычеркиваем числа, кратные только ранее найденным простым, а новые простые мы не находим и не и не используем.

То есть, мы с самого начала – по умолчанию – решили, что «последнее вычеркнутое» число мы будем запоминать, только если оно находится в пределах текущего поискового интервала (меньше maxNum), но так может вовсе и не оказаться. Идея была разумная: как мы можем запомнить «последнее вычеркнутое», если мы его вовсе не вычеркивали! Мы же можем вычеркнуть только в пределах текущего поискового интервала.

Значит, нам необходимо запоминать «последнее вычеркнутое» даже в том случае, если мы не вычеркивали. Ого! Вот это авантюра, вот это приписки! На самом деле, ничего страшного – просто, мы его вычеркнем потом – когда перейдем от текущего поискового интервала к следующему. Для этого, создавать список на удаление to_remove каждый раз придется чуть более аккуратно, чем ранее.

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

def add_primes(minNum, maxNum, prev_primes):

    '''добавляем простые числа и последние вычеркнутые числа'''

    nums = list(range(minNum, maxNum+1)

    for prime, last_removed in prev_primes.items():

        if last_removed < minNum :

            to_remove = range(last_removed + prime, maxNum+1, prime)

        else :

            to_remove = range(last_removed, maxNum+1, prime)

        for num in to_remove :

            nums[num - minNum] = 0

        prev_primes[prime] = to_remove[-1]

    # ищем новые простые

    for num in nums :

        # если равен нулю, то число вычеркнуто

        if num != 0:

            next_prime = num

            to_remove = range(next_prime * 2, maxNum+1, next_prime)

            for num1 in to_remove:

                nums[num1 - minNum] = 0

            if len(to_remove) > 0:

                prev_primes[next_prime] = to_remove[-1]

            else :

                prev_primes[next_prime] = 2 * next_prime

def get_n_primes(n):

    #Находит первые n или больше первых простых чисел

    minNum = 2

    maxNum = 2*n

    prev_primes = {}

    while len(prev_primes) < n:

        add_primes(minNum, maxNum, prev_primes)

        minNum = maxNum + 1

        maxNum *= 2

    return list(prev_primes.keys())

a = get_n_prime(100)

a = a[:100]

print(a)

Проверяем результат: (можете сравнить с готовыми таблицами простых чисел):.

[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, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

Желающие могут получить готовый код на onlinegdb.com: https://onlinegdb.com/sQhflSeJ3

Напоследок – вопрос для размышлений, на будущее. Хорошо, мы справились с задачей. Но мы справились типично «по-питонски»: с использованием словарей. Не все языки поддерживают такой тип данных. Как упоминалось выше, в языке Си есть аналог в виде struct, но это совсем не то – это можно считать словарем, но фиксированной длины, а в Python словарь «резиновый». Как построить алгоритм «раздвижного решета» для языка Си или С++?

Литература:

1.     Эратосфен. Статья в электронной энциклопедии «Википедия» https://ru.wikipedia.org/wiki/Эратосфен

2.     Гончаренко В.Е. «Определение простых чисел от века папируса до века ПК», журнал «Потенциал» № 1,  2010 г.

3.     Гончаренко В.Е. «Алгоритм создания коллекции простых чисел», журнал «Потенциал» № 3,  2010 г.

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому^[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

История[править | править код]

Этот метод описан во «Введении в арифметику» Никомаха Герасского. Никомах называет автором метода Эратосфена. То же делает и Ямвлих в своём комментарии к этому сочинению Никомаха.

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

Никомах,^[1] во 2-м веке н.э., объясняет, что метод решета “высеивает” простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа n каждое n-ное число в ряду нечётных чисел, начиная с n. Символически,

 Primes = {3,5,7,9,...}  Composites
 Composites = { 3n,5n,7n,9n,... for n in {3,5,7,9,...} }

Британец Хорслей,^[3] 16 веков спустя, горячо критикует это описание, заявляя что “истинный” метод Эратосфена “наверняка” был “гораздо умнее”, начиная с квадратов простых чисел прямо в процессе их распознавания:

 Composites = { n²,n²+2n,n²+4n,... for n in Primes }

Алгоритм[править | править код]

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

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

Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа p², потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, а они уже зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p² станет больше, чем n.^[3] Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p².

Пример для n = 30[править | править код]

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

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

Первое число в списке, 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² = 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² = 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

Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2  3     5     7           11    13          17    19          23                29

Псевдокод[править | править код]

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде^[4][5]:

Вход: натуральное число n
Выход: все простые числа от 2 до n.

Пусть A — булевый массив, индексируемый числами от 2 до n, 
изначально заполненный значениями true.

 для i = 2, 3, 4, ..., пока i2 ≤ n:
  если A[i] = true:
    для j = i2, i2 + i, i2 + 2i, ..., пока j ≤ n:
      назначить A[j] := false

 возвращаем: все числа i, для которых A[i] = true.

Сложность алгоритма[править | править код]

Сложность алгоритма составляет операций при составлении таблицы простых чисел до ^[6].

Доказательство сложности[править | править код]

При выбранном для каждого простого будет выполняться внутренний цикл^[7], который совершит действий. Сложность алгоритма можно получить из оценки следующей величины:

Так как количество простых чисел, меньших либо равных , оценивается как , и, как следствие, -е простое число примерно равно , то сумму можно преобразовать:

Здесь из суммы выделено слагаемое для первого простого числа, чтобы избежать деления на ноль. Данную сумму можно оценить интегралом

В итоге получается для изначальной суммы:

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»^[8].

Модификации метода[править | править код]

Неограниченный, постепенный вариант[править | править код]

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

 primes = {2,3,...}  { p², p²+p, ... for p in primes }

используя нотацию абстракции списков, где обозначает разницу между арифметическими прогрессиями.

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

Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами:

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², p²+p..])]

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

Перебор делителей[править | править код]

Решето Эратосфена часто путают с алгоритмами, которые поэтапно отфильтровывают^[en] составные числа, тестируя каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.^[10]

Широко известный функциональный код Дэвида Тёрнера 1975 г.^[11] часто принимают за решето Эратосфена,^[10] но на самом деле^[9] это неоптимальный вариант с перебором делителей:

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve [x in xs if x%p > 0]]

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

Сегментированное решето[править | править код]

Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году).^[5] При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок^[en].

Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.^[12] Данный метод известен с 1970-х годов и работает следующим образом:^[5][13]

1. Разделяем диапазон от 2 до n на отрезки (сегменты) некоторой длины Δ ≤ √n.
2. Находим все простые числа в первом отрезке, используя обычное решето.
3. Каждый из последующих отрезков оканчивается на некотором числе m. Находим все простые числа в отрезке следующим образом:
   1. Создаем булевый массив размера Δ
   2. Для каждого простого числа p ≤ √m из уже найденных, отмечаем в массиве как «непростые» все числа кратные p, перебирая числа с шагом в p, начиная с наименьшего кратного p числа в данном отрезке.

Если число Δ выбрано равным √n, то сложность алгоритма по памяти оценивается как O(√n), а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.^[13]

Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие √n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.^[14]

Решето Эйлера[править | править код]

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978 г. как решето с линейным временем работы (см. ниже).

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

[2] (3) 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...] 

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

В псевдокоде,

 primes = sieve [2..] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², ...p*xs])]

Решето только по нечётным числам[править | править код]

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

В псевдокоде:

 primes = [2, ...sieve [3,5..]] where
    sieve [p, ...xs] = [p, ...sieve (xs  [p², p²+2p..])]

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

Уменьшение объёма потребляемой памяти[править | править код]

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

Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.

Решето Эратосфена с линейным временем работы[править | править код]

Нижеследующий алгоритм находит составные числа как перечисление формулы

{ (piqjrk...) for p,q,r,... in primes, where i+j+k+... > 1 }

Этот алгоритм обнаруживает для каждого числа i в отрезке [2…n] его минимальный простой делитель lp[i] (lp от англ. least prime).

Также поддерживается список всех простых чисел — массив pr[], поначалу пустой. В ходе работы алгоритма этот массив будет постепенно заполняться.

Изначально все величины lp[i] заполним нулями.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

• lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.

Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

• lp[i] ≠ 0: это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].

В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p^[15].

Псевдокод[править | править код]

 Вход: натуральное число n

Пусть pr - целочисленный массив, поначалу пустой;
      lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями

 для i := 2, 3, 4, ..., до n: 
   если lp[i] = 0:
       lp[i] := i
       pr[] += {i}
   для p из pr пока p ≤ lp[i] и p*i ≤ n:
       lp[p*i] := p

Выход: все числа в массиве pr.

Сложность алгоритма на практике[править | править код]

Решето Эратосфена является популярным способом оценки производительности компьютера.^[16] Как видно из вышеизложенного доказательства сложности алгоритма, избавившись от константы и слагаемого очень близкого к нулю (ln (ln n – ln ln n) – ln ln 2 ≈ ln ln n), временная сложность вычисления всех простых чисел меньше n аппроксимируется следующим соотношением O(n ln ln n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).^[17]

Сегментированная версия имеет ту же операционную сложность O(n ln ln n),^[8]. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен O(√n/ln n).^[18]
Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за O(n) операций и занимает O(√n ln ln n/ln n) бит в памяти.^[17][19][18]

На практике оказывается, что оценка ln ln n не очень точна даже для максимальных практических диапазонов таких как 10¹⁶.^[19] Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения.^[8] Таким образом очень медленно растущий член ln ln n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания.^[8] Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.^[19]

Решето Эратосфена работает быстрее, чем часто сравниваемое с ним решето Аткина только для значений n меньших 10 ¹⁰ .^[20] Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом.^[21] С учетом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для n свыше 10 ¹³ , но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка».^[21] Однако раздел о сегментированной версии решета Эратосфена показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации.^[13][20] В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.

Использование нотации O большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов.^[8] Например, одна из вариаций решета Эратосфена известная как решето Притчарда^[17] имеет производительность O(n),^[19] но её базовая реализация требует либо алгоритма «одного большого массива»^[18] (то есть использования обычного массива, в котором хранятся все числа до n), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.^[19]

Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода факторизация.^[22] Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных.^[23][22] Для индексных алгоритмов часто используют кольцевую факторизацию.^[23][24] Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного n подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.^[25]

Несмотря на теоретическое ускорение, получаемое с помощью кольцевой факторизации, на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии.^[26] Рассмотрим наиболее существенные из них:

• Умножение и деление. При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).^[27]
• Оптимизация компилятора. Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.^[28]
• Кэш. Процессор использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.^[28]

Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов n и разных степеней кольцевой факторизации. E_i и P_i обозначения для решета Эратосфена и Питчарда соответственно, где индекс i означает степень кольцевой факторизации. E₀ и P₀ означают отсутствие факторизации.^[28]

n	E0	E1	E2	E3	E4	E5
500	0.00043	0.00029	0.00027	0.00048	0.00140	0.01035
5000	0.00473	0.00305	0.00254	0.00293	0.00551	0.03207
50000	0.05156	0.03281	0.02617	0.02578	0.03164	0.10663
500000	0.55817	0.35037	0.28240	0.28358	0.28397	0.47028
5000000	6.06719	3.82905	3.20722	3.25214	3.28104	3.38455

Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации E₂. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.

n	P0	P1	P2	P3	P4	P5
500	0.00147	0.00074	0.00050	0.00051	0.00095	0.00649
5000	0.01519	0.00777	0.00527	0.00453	0.00430	0.00973
50000	0.15507	0.08203	0.05664	0.04843	0.04180	0.04413
500000	1.60732	0.86254	0.61597	0.53825	0.47146	0.43787
5000000	16.47706	9.00177	6.57146	5.83518	5.27427	4.88251

С увеличением n соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне n = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.^[19]

См. также[править | править код]

• Решето Сундарама
• Решето Аткина
• Корекурсия

Примечания[править | править код]

Литература[править | править код]

• Эратосфеново решето // Элоквенция — Яя. — М. : Советская энциклопедия, 1957. — С. 141. — (Большая советская энциклопедия : [в 51 т.] / гл. ред. Б. А. Введенский ; 1949—1958, т. 49).
• Гальперин Г. «Просто о простых числах» // Квант. — 1987. — № 4. — С. 10-14,38.
• Неопубликованные материалы Л.Эйлера по теории чисел / РАН, Институт истории естествознания и техники, С.-Петерб. фил.; Сост. Матвиевская Г.П. [и др.]; Отв. ред. Невская Н.И. — СПб.: Наука, 1997. — ISBN 5-02-024847-9.
• Проф. Д.Ф.Егоров. Элементы теории чисел. — Государственное издательство Москва, 1923. (недоступная ссылка)
• Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

Ссылки[править | править код]

• Решето Эратосфена от М. Гарднера
• Алгоритм составления таблицы простых чисел от заданного до другого числа
• Реализация алгоритма поиска простых чисел на Java
• Доказательство сложности алгоритма
• Еще раз о поиске простых чисел

Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.

Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).

Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:

• Шаг 1: Переберите все элементы в заданном диапазоне.
• Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
• Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
• Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
• Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.

Пример: код Python для печати простого числа в заданном интервале.

 
# First, we will take the input: 
lower_value = int(input("Please, Enter the Lowest Range Value: ")) 
upper_value = int(input("Please, Enter the Upper Range Value: ")) 
 
print("The Prime Numbers in the range are: ") 
for number in range(lower_value, upper_value + 1): 
    if number > 1: 
        for i in range(2, number): 
            if(number % i) == 0: 
                break 
        else: 
            print(number) 

Выход:

Please, Enter the Lowest Range Value:  14 
Please, Enter the Upper Range Value:  97 
The Prime Numbers in the range are:  
17 
19 
23 
29 
31 
37 
41 
43 
47 
53 
59 
61 
67 
71 
73 
79 
83 
89 
97 

Заключение

В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.