• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Sito Eratostenesa

    Przeczytaj także...
    Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).
    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.

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

    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

    Eratostenes (gr. Ἐρατοσθένης Eratosthenes; ur. 276 p.n.e. w Cyrenie, zm. 194 p.n.e.) – grecki matematyk, astronom, filozof, geograf i poeta.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.

    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.

    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.

    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.
    

    Zobacz też[ | edytuj kod]

  • sito Atkina
  • Przypisy[ | edytuj kod]

    1. Eric W. Weisstein, Sieve of Eratosthenes, [w:] MathWorld [online], Wolfram Research [dostęp 2017-11-26] (ang.).

    Linki zewnętrzne[ | edytuj kod]

  • Animacja sita Eratostenesa




  • Reklama

    Czas generowania strony: 0.009 sek.