FANDOM


Sito Eratostenesa - metoda wyszukiwania liczb pierwszych polegająca na wypisaniu wszystkich liczb naturalnych z przedziału od 2 do pewnej liczby, a następnie na wykreślaniu z tego zbioru liczb złożonych.

Sito Eratostenesa jest przykładem algorytmu działającego na zasadzie wyszukiwania wyczerpującego.

Działanie metody Edytuj

Najpierw należy wypisać kolejno wszystkie liczby naturalne od 2 do n. Następnie oznacza się najmniejszą liczbę (na początku będzie to 2) jako liczbę pierwszą, jednocześnie wykreślając ze zbioru wszystkie jej wielokrotności. W kolejnym kroku znowu bierze się najmniejszą liczbę (pomijając wykreślone i te już rozpatrzone), oznacza ją jako pierwszą i wykreśla wszystkie jej wielokrotności.

Czynność tę powtarza się do momentu, w którym rozpatrywana liczba jest większa od pierwiastka z największej liczby w zbiorze (w tym przypadku oznaczonej jako n).

Wszystkie liczby, które nie zostały wykreślone, są liczbami pierwszymi.

Przykład Edytuj

Szukamy liczb pierwszych mniejszych bądź równych 25. Najpierw trzeba wypisać wszystkie liczby naturalne od 2 do 24.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 18, 20, 21, 22, 23, 24, 25

Pierwszą liczbą jest liczba 2. Oznaczamy tę liczbę jako liczbę pierwszą, a następnie wykreślamy wszystkie jej wielokrotności (oprócz niej samej).

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16 , 17, 18, 19, 20, 21, 22, 23, 24, 25

W kolejnym kroku robimy to samo z liczbą 3.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16 , 17, 18, 19, 20, 21, 22, 23, 24, 25

Idziemy dalej. Liczba 4 jest już wykreślona, wiec w następnym kroku analizujemy liczbę 5.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16 , 17, 18, 19, 20, 21, 22, 23, 24, 25

Kolejną analizowaną liczbą byłaby liczba 7. Nie musimy jej już jednak rozpatrywać, gdyż 7 > \sqrt{25} .

Liczbami pierwszymi w tym zbiorze są więc liczby 2, 3, 5, 7, 11, 13, 17, 19 i 23.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Więcej z Fandomu

Losowa wiki