Sito Erastotenesa

Sito Eratostenesa jest sposobem wyznaczania liczb pierwszych zaproponowanym przez greckiego matematyka Eratostenesa. Metoda sita (w założeniu eliminacja) polega na odrzucaniu liczb naturalnych będących wielokrotnościami liczb pierwszych.

Przykład:
Weźmy pod uwagę liczby naturalne z przedziału <2,20> (liczba 1 nie jest liczbą pierwszą więc ją pomijamy - tak stanowi algorytm).

Liczba 2 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności:
Pozostają liczby:
2,3,5,7,9,11,13,15,17,19

Kolejna liczba - 3 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności:
Pozostają liczby:
2,3,5,7,11,13,17,19

Kolejna liczba - 5 jest liczbą pierwszą - dokonujemy eliminacji jej wielokrotności (brak takich liczb w badanym przedziale):
Pozostają liczby:
2,3,5,7,11,13,17,19

Postępujemy podobnie z nastepnymi liczbami.
W przytoczonym przykładzie już po eliminacji liczby 3 pozostały tylko liczby pierwsze.

Podsumowując:
Dla danej liczby n wszystkie niewyeliminowane liczby mniejsze od n są liczbami pierwszymi.
 
Program (Turbo Pascal)
program Sito_Erastotenesa;
uses crt;
const
  zakres = 50;
var
  sito : array [2..zakres] of boolean;
  i,j : longint;
begin
  clrscr;
  for i:= 2 to zakres do sito [i] := true;
  for i:= 2 to zakres do 
    if sito [i] then
    begin
      writeln (i);    
      j:= 2;
      while i*j<=zakres do
      begin
        sito [i*j] := false;
        j:=j+1;
      end;
    end;
repeat until keypressed;
end.

Komentarze


link Silnią liczby naturalnej n nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie symboliczne n! (czytaj: n silnia) wprowadził w 1808 roku francuski matematyk Christian Kramp. Zgo


link Ciąg Fibonacciego to ciąg liczb naturalnych zwanych liczbami Fibonacciego określony rekurencyjnie w sposób następujący:F0 = 0F1 = 1Fn = Fn-1 + Fn-2, dla n ≥ 2Początkowe wartości tego ciągu to:


link program kwadratowe;uses crt;var x1,x2,x,r1,r2,delta,pierwiastek:real;    a,b,c,yw,x0:real;    kla:char;beginrepeat  clrscr;  writeln('Ten program rozwiazuje rownania kwadratowe axx+by+c');  w


link   program NWW;uses crt;var a,b,d:longint;     begin         clrscr;         writeln(' Program obliczajacy NWW ');         writeln;         write('wprowadz a:');