Простые числа в промежутке от 2 до n можно найти, используя решето Эратосфена.

     В последовательности чисел 2, 3, 4, ... , n вычеркнем каждое число после 2. Первое невычеркнутое число - простое (число 3). Далее вычеркиваем каждое третье число после 3 (при вычеркивании учитываются уже отброшенные числа). Первое невычеркнутое число - простое (5). Теперь вычеркиваем каждое пятое число и т.д. до тех пор, пока не дойдем до числа, большего √n. Все оставленные числа являются простыми. Действительно, если положительное число n>1 не делится ни на какое положительное число, не большее √n, то оно является простым.

     Составим программу. Размерность массива простых чисел должна быть задана в основной программе. Количество простых чисел равняется j.

     Программа работает следующим образом. Сначала задаются первые два простые числа (2 и 3). Потом все непарные числа m от 5 до n проверяются, не являются ли они простыми. Эта проверка заключается в делении числа m последовательно на все простые числа от 3 до числа, не большего √m. Если число m не имеет простых множителей в интервале (3,5, ... , √m), то оно является простым и осуществляется его запись в массив p.

{erat.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

 

const r=300;

type ar=array[1..r] of integer;

var n,kol,i:integer;

  prost:ar;

procedure erat(n1:integer; var p:ar; var j:integer);

{j - кол-во простых чисел}

var m,k,s:integer;

    b:boolean;{b - флаг, если b=true, то m - простое, иначе - составное}

begin

  p[1]:=2;p[2]:=3; {задание первых 2 простых чисел}

  j:=2; {задание номера второго простого числа}

  m:=3; {задание начального значение числа m (m=3)}

  repeat {перебор нечетных чисел от 5 до n}

    m:=m+2; s:=trunc(sqrt(m)+0.1); b:=true; k:=2;

    while b and (p[k]<=s) do

      if m mod p[k]=0 then b:=false else k:=k+1;

    if b then begin j:=j+1; p[j]:=m; end;{если b=true, то m - простое}

  until m>n1-2

end;

 

begin

  writeln('Введите n');

  readln(n);

  erat(n,prost,kol);

  writeln('Простые числа на промежутке от 2 до ',n);

  for i:=1 to kol do

  writeln(prost[i]);

end.