Zaproszenie

Witamy na stronach edukacyjnych

dla nauczycieli, studentów i uczniów szkół średnich w zakresie

informatyki i systemów mikroprocesorowych

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.

 

Współpracujemy z:

Strona powstała dzięki współpracy z Templatka.pl - serwisem oferującym Joomla Szablony, Moduły i inne materiały do tego dobrego systemu CMS - Zarówno free jak i komercyjne. Polecamy nasz Katalog firm Empex.pl oraz językowe kursy dofinansowane z Unii Europejskiej i serwis z informacjami na temat systemu blogowego Nucleus CMS.
Wspieramy inicjatywę: Uniwersytety Dla Wszystkich - zainicjowaną przez Uniwersytet Warszawski, w zakresie technik komputerowych
Wspieramy informatycznie stronę sponsora: Hydraulic Hammers Buildplant.eu - firma zajmująca się dystrybucją różnych maszyn budowlanych

Statystyka

Members : 369
Content : 50
Content View Hits : 2042034

Online

We have 14 guests online
Designed by Templatka.pl dla ZS Zychlin