Sito Eratostenesa: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
wyrzucenie kodów źródłowych, dodanie pseudokodu |
WP:SK, poprawa linków |
||
Linia 3:
|wielkość grafika= 154 KB
|opis= Przykładowe działanie Sita Eratostenesa
|rodzaj=
|struktura=[[Tablica (informatyka)|Tablica]], [[lista]]
|czas= O((n log n)(log log n))
Linia 10:
'''Sito Eratostenesa''' - przypisywany [[Eratostenes|Eratostenesowi z Cyreny]] [[algorytm]] wyznaczania [[liczba pierwsza|liczb pierwszych]] z zadanego przedziału <math>[2,n]\;</math>.
== Algorytm ==
Ze zbioru liczb naturalnych z przedziału <math>[2,n]\;</math>, tj. <math>\{2, 3, 4, \dots, n\}</math>, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest <math>4, 6, 8, \dots</math>.
{| style="border: 1px black solid; text-align: center;" rules=all cellspacing=0 cellpadding=4 align=center
Linia 291:
|}
Powyższy algorytm można zapisać w postaci następującego
'''Wejście''': liczba całkowita ''n'' > 1
Linia 303:
'''Wyjście''': wartości ''i'' takie, że ''A''[''i''] zawiera wartość '''true'''.
== Zobacz też ==
|