Создать программу, генерирующую множество простых чисел — Pascal(Паскаль)

При работе с данным упражнением следует воспользоваться алгоритмом «решето Эратосфена» нахождения простых чисел, не превышающих заданное натуральное число. Основная идея алгоритма заключается в «просеивании» исходного множества, включающего в себя все натуральные числа, не превышающие заданное. В результате такого «просеивания» из исходного множества удаляются все имеющиеся в нем составные числа: сначала — кратные 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. 

Leave a Comment

93 − 87 =