При работе с данным упражнением следует воспользоваться алгоритмом «решето Эратосфена» нахождения простых чисел, не превышающих заданное натуральное число. Основная идея алгоритма заключается в «просеивании» исходного множества, включающего в себя все натуральные числа, не превышающие заданное. В результате такого «просеивания» из исходного множества удаляются все имеющиеся в нем составные числа: сначала — кратные 2, затем — кратные 3 и т.д., на i-том шаге алгоритма из множества удаляются числа, кратные числу j, не удаленному ранее и следующему за простым k, кратность которому была признаком удаления чисел на (i-1)-ом шаге алгоритма.
Принцип алгоритма:
· Сформируем множество BEGINSET состоящее из всех целых чисел в диапазоне от 2 до n.
· В множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1.
· Цикл до тех пор пока множество BEGINSET не станет пустым:
1. Взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
2. Удалить из BEGINSET число NEXT и все другие числа кратные ему.
Program Primer_numbers_detect;
{Выделение всех простых чисел из первых N целых}
const
N = 255; {Количество элементов исходного множества}
type
SetOfNumber = set of 1..N;
var
n1,next,i : Word; {Вспомогательные переменные}
BeginSet, {Исходное множество}
PrimerSet : SetOfNumber; {Множество простых чисел}
begin
BeginSet := [2..N] ; {Создаем исходное множество}
PrimerSet:= [1]; {Первое простое число}
next:= 2; {Следующее простое число}
while BeginSet <> [] do {Начало основного цикла}
begin
n1 := next;{n1-число,кратное очередному простому (next)}
{Цикл удаления из исходного множества непростых чисел:}
while n1 <= N do
begin
Exclude(BeginSet,n1);
n1 := n1+next {Следующее кратное}
end; {Конец цикла удаления}
Include(PrimerSet,next);
{Получаем следующее простое, которое есть первое не вычеркнутое из исходного множества}
repeat
inc(next)
until (next in BeginSet) or (next > N)
end; {Конец основного цикла}
{Выводим результат:}
for i := 1 to N do
if i in PrimerSet then Write(i:8);
writeLn;
end.