Sito Eratostenesa^(*)

Naciśnij i zagraj w sito Eratostenesa.

Celem gry na tym poziomie jest wyznaczenie liczb pierwszych mniejszych od 40, to znaczy należy pozostawić na tablicy liczby pierwsze, a usunąć liczby niepierwsze. Przypominamy: liczby pierwsze to takie liczby naturalne, które są podzielne wyłącznie przez 1 i przez samą siebie. Każda liczba pierwsza ma więc dwa dzielniki naturalne. Liczba 1 ma tylko jeden dzielnik i dlatego nie jest liczbą pierwszą.

Jak wyznaczyć liczby pierwsze mniejsze od 40?

Można oczywiście sprawdzać, czy każda z liczb od 1 do 40 jest podzielna przez inną liczbę, różną od 1 i od niej samej. Zajmie to jednak dużo czasu. Już w starożytności Eratostenes znalazł szybki sposób, aby bez sprawdzania podzielności wyznaczyć liczby pierwsze. W papirusie, na którym były napisane kolejne liczby naturalne, wypalał dziurki w miejscach, gdzie były liczby niepierwsze. Otrzymał w ten sposób jakby "sito", które odsiało zbędne liczby, a pozostawiło liczby pierwsze. Wielkim odkryciem, dzięki któremu Eratostenes i jego "sito" przetrwało do dzisiejszych czasów, jest jednak nie to, że wyznaczył liczby pierwsze, ale sposób, w jaki usunął zbędne liczby. Eratostenes nie zastanawiał się nad dzielnikami każdej liczby, tylko usuwał wielokrotności liczb pierwszych począwszy od liczby 2.

Zrób więc tak jak Eratostenes. Usuń liczbę 1. Pozostaw liczbę 2 i usuń jej wielokrotności: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40.  Następnie pozostaw 3 jako liczbę pierwszą (dlaczego?) i usuń jej wielokrotności: 9,15, 21, 27, 33, 39. Następnie pozostaw 5, jako liczbę pierwszą (dlaczego?) i usuń jej wielokrotności: 25, 35.
I to już koniec, zostały same liczby pierwsze!

Zagraj teraz na wyższych poziomach.
Za każdy dobry ruch, czyli za usunięcie liczby, która nie jest pierwsza, otrzymasz 1 pkt, zaś za zły ruch, czyli za usunięcie liczby pierwszej, otrzymasz karę -1 pkt. Zły ruch można cofnąć, naciskając prawy przycisk myszy, ale straconego punktu już nie możesz odzyskać.
W czasie gry możesz uzyskać informację o stanie gry, naciskając klawisz "Pomoc". Program podaje, ile jeszcze liczb pozostało do usunięcia i ile liczb usunąłeś źle. Korzystając z pomocy, tracisz jednak 1 pkt. Można w czasie gry rozpocząć ją od nowa lub zmienić poziom gry, naciskając klawisz "Nowa gra".

Powodzenia !

(*) Aplet wykorzystany w tej lekcji powstał do gimnazjalnego cyklu "Eureka". Więcej informacji o serii na stronie www.wszpwn.com.pl.

A teraz kilka problemów związanych z sitem i liczbami pierwszymi.

Problem 1.
Dlaczego "sito" jest dobre, to znaczy dlaczego jesteśmy pewni, że sposobem Eratostenesa wyznaczymy wszystkie liczby pierwsze w danym zakresie?

Problem 2.
Jak długo należy kontynuować sposób Eratostenesa, aby mieć pewność, że wyznaczyliśmy wszystkie liczby pierwsze w danym zakresie?

Problem 3.
Czy liczb pierwszych jest skończenie, czy nieskończenie wiele?

Problem 4.
Ile jest liczb pierwszych w danym przedziale?

Odpowiedzi

Problem 1.
Wystarczy uogólnić odpowiedzi na pytania "dlaczego?" sformułowane na początku strony, przy opisie sposobu Eratostenesa. Wyjaśnimy to na przykładzie liczby 7. Załóżmy, że zostały już usunięte wszystkie wielokrotności liczby 2, wszystkie wielokrotności liczby 3 i wszystkie wielokrotności liczby 5. Następna nieusunięta liczba, czyli 7, musi być liczbą pierwszą. Nie jest ona podzielna przez żadną mniejszą liczbę naturalną (oczywiście, poza liczbą 1), ponieważ w przeciwnym wypadku zostałaby usunięta jako wielokrotność. Ze zrozumiałych względów nie może być również podzielna przez liczbę większą od siebie. Tak więc 7 jest liczbą pierwszą i każda liczba nie usunięta sposobem Eratostenesa jest liczbą pierwszą (ale sposób ten musi być doprowadzony do końca - patrz następny problem). Nie ma też możliwości, aby pozostała liczba złożona, ponieważ każda taka liczba jest podzielna przez jakąś liczbę od niej mniejszą.

Problem 2.
Wyjaśnimy to na przykładzie liczb mniejszych od 40. Załóżmy, że usunęliśmy wszystkie wielokrotności liczby 2, wszystkie wielokrotności liczby 3 i wszystkie wielokrotności liczby 5. Nie trzeba już wykreślać wielokrotności liczby 7, ponieważ 2*7 było usunięte jako wielokrotność liczby 2, 3*7 było usunięte jako wielokrotność liczby 3, 5*7 było usunięte jako wielokrotność liczby 5, zaś 7*7 przekracza 40.  Tak więc sposób Eratostenasa jest bardzo szybki i wystarczy prowadzić go do pierwiastka kwadratowego z liczby, do jakiej chcemy wyznaczyć liczby pierwsze. Np. dla 100 liczb wystarczy usunąć wielokrotności liczby 7, gdyż pierwiastek kwadratowy ze 100  wynosi 10, a następna nieusunięta liczba to 11. Co ciekawe, nie wynaleziono do tej pory szybszego sposobu na wyznaczanie wszystkich liczb pierwszych (w danym zakresie), niż sito Eratostenesa. Programy komputerowe również stosują ten sposób. Oto prosty program w języku Pascal wypisujący liczby pierwsze do 2400.

program Sito_Eratostenesa;
uses crt;
const max=2400;
var liczba,n:longInt;
    t:array[1..max] of longInt;
begin
   clrScr;
   for liczba:=2 to round(sqrt(max)) do
     if t[liczba]=0 then 
        for n:=2 to max div liczba do 
            t[liczba*n]:=1;
   for n:=2 to max do 
       if t[n]=0 then write(n:5);
   readLn;
end.

Problem 3.
Gdyby liczb pierwszych było skończenie wiele wzięlibyśmy ich iloczyn i dodali do niego 1. Gdyby tak utworzona liczba okazała się liczbą pierwszą, to mielibyśmy następną liczbę pierwszą. Gdyby jednak okazała się liczbą złożoną, to musiałaby się dzielić przez jakąś nową liczbę pierwszą nie wchodzącą w skład iloczynu, ponieważ iloczyn liczb pierwszych z dodaną jedynką nie może się dzielić przez żaden czynnik tego iloczynu. W obu przypadkach mamy więc nową liczbę pierwszą, czyli liczb pierwszych jest nieskończenie wiele.

Problem 4.
Jest to trudny problem, który bada się metodami matematyki wyższej. Wynik jest jednak zaskakująco prosty. Mianowicie: liczb pierwszych mniejszych od n jest , gdzie ln oznacza logarytm naturalny. Więcej na ten temat dowiesz się na lekcji "Zgadywanka" lub z podręcznika "Matematyka przyjemna i pożyteczna - klasa 2" do zakresu rozszerzonego. Zachęcamy również do samodzielnego wyszukania opracowań na ten temat.