Sito Eratostenesa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Sito Eratostenesa – przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału

Sito Atkina (nazywane też sitem Atkina-Bernsteina) – algorytm autorstwa A.O.L. Atkina i D.J. Bernsteina służący do wyszukiwania liczb pierwszych w dużych przedziałach. Metoda działa podobnie, jak sito Eratostenesa, jednak dzięki wykorzystaniu bardziej wyrafinowanej teorii jest szybsza i wymaga znacznie mniej pamięci.Eratostenes (gr. Ἐρατοσθένης Eratosthenes; ur. 276 p.n.e. w Cyrenie, zm. 194 p.n.e.) – grecki matematyk, astronom, filozof, geograf i poeta.

Algorytm[ | edytuj kod]

Ze zbioru liczb naturalnych z przedziału tj. wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest

Pseudokodem nazywany jest taki sposób zapisu algorytmu, który, zachowując strukturę charakterystyczną dla kodu zapisanego w języku programowania, rezygnuje ze ścisłych reguł składniowych na rzecz prostoty i czytelności. Pseudokod nie zawiera szczegółów implementacyjnych (jak np. inicjalizacja zmiennych, alokacja pamięci), często też opuszcza się w nim opis działania podprocedur (jeśli powinien być on oczywisty dla czytelnika), zaś nietrywialne kroki algorytmu opisywane są z pomocą formuł matematycznych lub zdań w języku naturalnym.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

Według tej samej procedury postępujemy dla liczby 5.

Następnie dla 7 aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

Wykreślanie powtarzamy do momentu, gdy liczba której wielokrotność wykreślamy, będzie większa niż

Dla danej liczby wszystkie niewykreślone liczby mniejsze, bądź równe są liczbami pierwszymi.

Powyższy algorytm można zapisać w postaci następującego pseudokodu:

Wejście: liczba całkowita n > 1
 
Niech A będzie tablicą typów logicznych indeksowaną liczbami całkowitymi od 2 do n
początkowo wypełniona wartościami true
 
 for i := 2, 3, 4, ..., nie więcej niż 
  if A[i] = true:
    for j :=  2*i, 3*i, 4*i, ..., nie więcej niż n :
      A[j] := false
 
Wyjście: wartości i takie, że A[i] zawiera wartość true.


Podstrony: 1 [2] [3]




Reklama