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.683 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


25
komentarze: 37 | wyświetlenia: 2565
19
komentarze: 11 | wyświetlenia: 4553
8
komentarze: 31 | wyświetlenia: 2726
58
komentarze: 20 | wyświetlenia: 80680
14
komentarze: 8 | wyświetlenia: 100811
31
komentarze: 8 | wyświetlenia: 56551
27
komentarze: 10 | wyświetlenia: 20342
23
komentarze: 5 | wyświetlenia: 19532
11
komentarze: 2 | wyświetlenia: 5274
9
komentarze: 3 | wyświetlenia: 15203
8
komentarze: 41 | wyświetlenia: 3833
12
komentarze: 3 | wyświetlenia: 29779
49
komentarze: 18 | wyświetlenia: 64976
37
komentarze: 9 | wyświetlenia: 28519
11
komentarze: 2 | wyświetlenia: 33152
 
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