Урок 12

Алгоритм Евклида.

Теорема Евклида.

Каждое натуральное число можно представить в виде произведения простых чисел.

Простым числом называется число, которое делится только на само себя и единицу. 

Для нахождения простых чисел используют простой и очень эффективный алгоритм - решето Эратосфена.

Представим себе ряд натуральных чисел в виде линейного массива, индексы которого будут в диапазоне от 1 до N. Индексы будем использовать в качестве значений натуральных чисел. В массиве будет находиться признак числа - "вычеркнули"  и "невычеркнули", которые будут иметь соответственно значения false и true.

q:=round(sqrt(n));

for i:=2 to q do

 if a[i] then begin

  j:=i*i;

   while j<=n do begin

    a[j]:=false;

    j:=j+1;

 end;

end;