Практика программирования (Бейсик, Си, Паскаль)


Задачи,советы и ответы - часть 37


простых чисел. На длинном папирусе он выписал числа 2, 3, 4, ... , 1000. Затем, сохранив первое число 2, он проколол каждое второе число, т. е. все четные числа, делящиеся на 2. В следующий раз, пропустив второе, не проколотое число 3, удалил после него каждое третье число, т. е. все числа, делящиеся на 3. Такая же участь постигла и каждое пятое число после 5, каждое седьмое число после 7 и т. д. К концу эксперимента на папирусе остались не проколотыми только простые числа. Возможно, что Эратосфен не догадался вдвое облегчить свою работу и использовать вдвое более короткий папирус, изначально выписав на нем только нечетные, числа. Зато сейчас мы составим программу, которая использует идею Эратосфена и находит все простые числа среди первых maxk нечетных чисел.

Совет 1 (общий)

Сформируем массив is, i-й элемент которого будет представлять нечетное число 2*1+3 и равняться 1, если 1-е число еще не "проколото", и равняться 0 в противном случае. Действуем по алгоритму Эратосфена — принимаем 3 в качестве первого нечетного простого числа и присваиваем нулевые значения каждому третьему элементу is. В качестве второго нечетного простого числа принимается следующая "не проколотая" позиция, соответствующая 5. "Прокалываем" каждую пятую позицию в is и т. д. В Бейсике идентификатор is является служебным словом, поэтому в программе его пришлось заменить на isi.

Совет 2 (Паскаль)

Решето Эратосфена очень изящно выглядит с применением данных типа множество (set). Регулярное множество, содержащее отрезок чисел натурального ряда, легко формируется с помощью интервального набора данных. К множеству можно добавлять новые элементы (операция сложения), исключать ненужные (операция вычитания), проверять принадлежность данного элемента множеству (операция in). Единственный недостаток множеств в Паскале — ограничение на количество элементов (не более 255).

Программа 2_22.bas

DEFINT A-Z CLS

МАХК=500 DIM ISI(MAXK+1)

FOR I=0 ТО МАХК-1: IS1(I)=1: NEXT I




- Начало -  - Назад -  - Вперед -