Cтраница 2
Типичной задачей, предлагаемой обучаемым во вводных курсах по обучению программированию, является решето Эратосфена - алгоритм для вычисления простых чисел, не превышающих некоторого заданного числа N. Основная идея этого алгоритма заключается в том, что все числа от 2 до N включительно располагаются в один ряд в порядке возрастания до тех пор, пока ряд не будет исчерпан, после чего повторяются следующие действия: определяется самое левое число ряда, которое затем удаляется из него вместе со всеми числами этого ряда, делящимися на это число без остатка. Определенное таким образом каждый раз самое левое число ряда представляет собой простое число. [16]
Представим себе, что мы проходим бесконечную последовательность надежных пар и ( на манер решета Эратосфена, служащего для отсеивания простых чисел от составных) вычеркиваем из нее все надежные пары, принадлежащие последовательности Фибоначчи. Получив ее, мы можем вычеркнуть вторую бесконечную последовательность Фибоначчи, все пары которой надежны. Процесс вычеркивания никогда не обрывается. [17]
Другим известным примером ленивой программы, результатом работы которой будет список всех простых чисел, является решето Эратосфена. [18]
Для составления таблицы простых чисел, не превосходящих данного N, существует простой способ, называемый решетом Эратосфена. Он состоит в нижеследующем. [19]
Для составления таблицы простых чисел, не превосходящих данного целого N, существует простой способ, называемый решетом Эратосфена. Он состоит в следующем. [20]
Отметим, что значения тг ( 104) и тг ( 5 103) легко вычисляются с помощью решета Эратосфена. [21]
В качестве примера использования этой формы записи здесь приводится функция языка Miranda для вычисления ( бесконечного) списка простых чисел с помощью решета Эратосфена, описанная в гл. [22]
Эратосфен, греческий философ ( 230 г. до н.э.), составил алгоритм для нахождения простых чисел. Этот метод называется решетом Эратосфена. Простым числом называется целое число, которое не делится ни на одно число, кроме единицы или самого себя. [23]
Простым числом называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом решета Эратосфена, идея которого заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [ л / 2 ] ( целая часть числа), кроме самих этих чисел. [24]
Это название происходит от переданного нам еще из древности термина решето Эратосфена. [25]
В качестве примера рассмотрим следующую программу решения задачи Иосифа ( Флавия), которая служит интересным контрастом решету Эратосфена. [26]
Первыми задачами о простых числах были такие: как часто они расположены в натуральном ряде и как далеко они отстоят друг от друга. Таким алгоритмом является решето Эратосфена ( 3 в. Евклид в Началах указал способ нахождения наибольшего общего делителя двух чисел ( алгоритм Евклида), следствием к-рого является теорема об однозначном разложении натуральных чисел на простые сомножители. [27]
Приводимые ниже результаты моделирования иллюстрируют последствия хранения программы и ( или) данных во внешней памяти. За единицу времени приняты его затраты в ситуации, когда и программа, и данные находятся во внутренней памяти транспьютера. Первая программа ( решето Эратосфена) представляет собой крайний случай, так как в ней значительное место занимают небольшие циклы, содержащие многочисленные обращения к данным; в ней отсутствуют параллельность, обмен информацией между транспьютерами и даже операции умножения и деления. [28]
Один из первых алгоритмов для поиска простых чисел принадлежит древнегреческому математику Эратос-фену, жившему в третьем веке до нашей эры. Алгоритм его, получивший название решета Эратосфена, состоит в том, что выписываются подряд все натуральные числа и вычеркивается каждое второе число, большее двух, потом каждое третье, большее трех, потом каждое пятое, большее пяти ( каждое четвертое уже было вычеркнуто, когда вычеркивалось каждое второе), и так далее. [29]
Простые числа, служащие для образования всех чисел, являются по самому их определению элементами, остающимися в натуральном ряде, если убрать из него числа с собственными делителями. Это определение некоторым образом отрицательно, откуда возникает подозрение об отсутствии единого метода для обнаружения свойств простых чисел, ибо мы скорее знаем, чем не являются эти числа, чем то, чем они являются. Единственный метод, принятый для их изучения, - это метод решета Эратосфена. [30]