Login lub e-mail Hasło   

Sito Eratostenesa

Jak prosto znaleźć wszystkie liczby pierwsze w zadanym przedziale metodą znaną jako Sito Eratostenesa.
Wyświetlenia: 11.794 Zamieszczono 29/10/2006

Wstęp

Często spotykamy się z problemem znalezienia w danym przedziale wszystkich liczb pierwszych. Można to łatwo zrobić sprawdzając po kolei każdą z nich, czy jest złożona. Rozwiązanie to jednak nie byłoby efektywne. Jest inna, szybsza metoda rozwiązanie tego problemu. Jest to tzw. "sito Eratostenesa". Nazwa pochodzi od tego, że wszystkie liczby są po kolei przesiewane i usuwane są wszystkie wielokrotności danej liczby. Żeby wszystko stało się jaśniejsze przejdźmy do przykładu.

 

Przykład

Znajdźmy na przykład wszystkie liczby pierwsze od 1 do 20. Liczby złożone będą po kolei "usuwane" w sposób podany niżej. Na początku nasz przedział wygląda następująco:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Cała idea tego algorytmu polega na tym, że "idziemy" od lewej strony przedziału poczynając od liczby 2 i gdy liczba ta nie została wcześniej skreślona to skreślamy wszystkie jej wielokrotności w danym przedziale oprócz niej samej.

Tak więc zaczynamy od liczby 2. Nie jest ona skreślona, więc skreślamy jej wielokrotności oprócz niej samej. W tym przypadku są to liczby: 4, 6, 8, 10, 12, 14, 16, 18, 20.

Po skreśleniu (usunięciu) wyżej wymienionych liczb otrzymujemy:

1 2 3   5   7   9   11   13   15   17   19  

Kolejną liczbę, jaką napotykamy po 2 jest liczba 3. Nie została ona wcześniej skreślona, więc skreślamy wszystkie jej wielokrotności w naszym przedziale od 1 do 20 oprócz niej samej. Proszę zauważyć, iż niektóre wielokrotności liczby 3 zostały już skreślone wcześniej. Liczby, które w tym przypadku skreślimy to: 6, 9, 12, 15, 18. Po tej operacji otrzymamy:

1 2 3   5   7       11   13       17   19  

Kolejną liczbę, jaką napotkamy idąc od lewej to 4. Ponieważ została ona już wcześniej skreślona to nie wykonujemy już żadnych dodatkowych skreśleń.

Proszę zauważyć, że w naszym przedziale zostały już tylko liczby pierwsze. Musimy jeszcze skreślić liczbę 1:

  2 3   5   7       11   13       17   19  

W sicie Eratostenesa może pojawić się jeden problem - a mianowicie do której liczby mamy dojść idąc od lewej od liczby 2, aby w danym przedziale zostały nam tylko liczby pierwsze? Moja odpowiedź brzmi do zaokrąglonego w dół pierwiastka kwadratowego największej liczby z danego przedziału. W naszym przypadku największą liczbą jest 20. Pierwiastek kwadratowy z 20 to około 4,47. Gdy zaokrąglimy tą liczbę w dół to otrzymamy 4. I tylko do tej liczby doszedłem w przykładzie powyżej. Teraz postaram się wytłumaczyć, dlaczego akurat dochodzimy do tej liczby. Każda liczba złożona w danym przedziale to iloczyn dwóch innych liczb (nie muszą być one koniecznie pierwsze). Liczby te mogą być równe sobie - wtedy wartość tych liczb to pierwiastek kwadratowy z danej liczby złożonej. Jednakże, gdy liczby te nie są sobie równe - to jedna jest większa, a druga mniejsza. Mniejsza z tych liczb jest mniejsza od pierwiastka kwadratowego z danej liczby złożonej. Tak więc, aby skreślić daną liczbę złożoną musimy dojść (gdy idziemy po kolei od 2) do tej mniejszej liczby, nie musimy wcale dochodzić do tej większej.

Podobne artykuły


29
komentarze: 55 | wyświetlenia: 24148
10
komentarze: 7 | wyświetlenia: 6110
58
komentarze: 20 | wyświetlenia: 81180
14
komentarze: 8 | wyświetlenia: 101483
31
komentarze: 8 | wyświetlenia: 58593
27
komentarze: 10 | wyświetlenia: 20881
24
komentarze: 5 | wyświetlenia: 20705
11
komentarze: 2 | wyświetlenia: 5431
9
komentarze: 3 | wyświetlenia: 15385
8
komentarze: 41 | wyświetlenia: 4315
12
komentarze: 3 | wyświetlenia: 30407
49
komentarze: 18 | wyświetlenia: 65805
37
komentarze: 9 | wyświetlenia: 29299
11
komentarze: 2 | wyświetlenia: 33541
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska