Урок 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; |