Liczby pierwsze do 1000: tablica
Liczba pierwsza ma dokładnie dwa dzielniki naturalne: jedynkę i samą siebie. Poniżej tysiąca jest ich sto sześćdziesiąt osiem, a najmniejsza z nich to dwójka, jedyna parzysta w całym zbiorze. Tablica niżej zawiera je wszystkie, a pole obok sprawdza dowolną liczbę i pokazuje, które dzielniki trzeba było przetestować.
Liczba naturalna od 1 do 1 000 000 000 000.
Liczba 997 jest pierwsza.
Wystarczyło sprawdzić liczby pierwsze do 31, czyli do części całkowitej z pierwiastka z 997. Żadna z nich nie dzieli tej liczby.
Sufit sprawdzania: √(997) = 31
- Do jakiego dzielnika trzeba sprawdzaćd ≤ √(997) = 31
- Sprawdzone dzielniki pierwsze2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
- Wniosek997 jest liczbą pierwszą
Jedynka nie jest zaznaczona: nie jest ani liczbą pierwszą, ani złożoną.
Jak to policzyć
- Odrzuć oczywiste przypadkiJedynka nie jest ani pierwsza, ani złożona. Każda liczba parzysta większa od dwójki jest złożona, bo dzieli się przez dwa. Każda liczba kończąca się piątką i większa od piątki jest złożona, bo dzieli się przez pięć. Te trzy obserwacje odrzucają większość kandydatów bez jednego dzielenia.
- Policz pierwiastek z liczbyWystarczy sprawdzać dzielniki nie większe od pierwiastka kwadratowego z badanej liczby. Gdyby liczba miała dzielnik większy od pierwiastka, to drugi czynnik tego samego iloczynu byłby od pierwiastka mniejszy i znalazłbyś go wcześniej. Dla liczby 997 wystarczy więc sprawdzić dzielniki do trzydziestu jeden.
- Sprawdzaj wyłącznie liczby pierwszeNie ma sensu dzielić przez cztery, sześć czy dziewięć: jeśli liczba dzieli się przez cztery, to dzieli się też przez dwa, więc odpadła już wcześniej. Kandydatami są wyłącznie liczby pierwsze nie większe od pierwiastka, czyli dla liczb trzycyfrowych najwyżej jedenaście testów.
- Wyciągnij wniosekJeżeli żaden ze sprawdzonych dzielników nie dzieli liczby bez reszty, liczba jest pierwsza. Jeżeli któryś dzieli, liczba jest złożona i znalazłeś przy okazji jej najmniejszy dzielnik większy od jedynki, czyli pierwszy krok rozkładu na czynniki pierwsze.
Przykład z matury
Sito Eratostenesa na przykładzie liczb od 1 do 30
Sito to metoda wykreślania, a nie sprawdzania. Wypisujesz liczby od dwóch do trzydziestu, zakreślasz dwójkę i wykreślasz wszystkie jej wielokrotności: cztery, sześć, osiem i tak dalej aż do trzydziestu. Pierwsza niewykreślona liczba to trójka, więc ją zakreślasz i wykreślasz jej wielokrotności: sześć, dziewięć, dwanaście, piętnaście. Kolejna niewykreślona to piątka i powtarzasz to samo.
Po piątce można przestać, bo pierwiastek z trzydziestu jest mniejszy od sześciu, a każda liczba złożona nie większa od trzydziestu ma dzielnik nie większy od pierwiastka z niej. To, co zostało niewykreślone, to komplet liczb pierwszych w tym zakresie: dwa, trzy, pięć, siedem, jedenaście, trzynaście, siedemnaście, dziewiętnaście, dwadzieścia trzy oraz dwadzieścia dziewięć. Dziesięć liczb na trzydzieści.
Po co liczby pierwsze na maturze
Egzamin nie pyta wprost, czy dana liczba jest pierwsza, ale opiera się na liczbach pierwszych w trzech miejscach naraz. Pierwsze to rozkład na czynniki, od którego zaczyna się skracanie ułamków, wyznaczanie największego wspólnego dzielnika i upraszczanie pierwiastków. Drugie to dowody podzielności, w których wyłącza się wspólny czynnik przed nawias i pokazuje, że jest on pierwszy albo że iloczyn zawiera potrzebny czynnik.
Trzecie miejsce to zadania o resztach z dzielenia, gdzie dzielnikiem prawie zawsze jest liczba pierwsza, najczęściej trzy, pięć albo siedem. Wynika to z własności, która przy liczbach złożonych nie zachodzi: iloczyn dwóch liczb dzieli się przez liczbę pierwszą tylko wtedy, gdy dzieli się przez nią któryś z czynników. To ona pozwala z podzielności iloczynu wnioskować o czynnikach.
Dlaczego jedynka nie jest liczbą pierwszą
Definicja mówi, że liczba pierwsza to liczba naturalna mająca dokładnie dwa różne dzielniki naturalne. Jedynka ma jeden, więc definicji nie spełnia. Nie jest też złożona, bo liczba złożona ma więcej niż dwa dzielniki. Jedynka stoi po prostu poza tym podziałem i jest to świadoma decyzja, a nie wyjątek dla wygody.
Powód jest głębszy niż zliczanie dzielników. Gdyby jedynka była pierwsza, rozkład liczby na czynniki pierwsze przestałby być jednoznaczny: liczbę sześć dałoby się zapisać jako iloczyn dwójki i trójki, ale także jako iloczyn jedynki, dwójki i trójki, i tak dalej bez końca. Jednoznaczność rozkładu jest zaś tym, na czym stoi cała reszta rachunków w tym dziale. Zadania z bazy CKE z tego materiału zebraliśmy we wpisie z zadaniami z liczb rzeczywistych.
Jak gęsto leżą liczby pierwsze
Tablica wyżej pokazuje coś, czego sama definicja nie zdradza: liczby pierwsze rzedną. W pierwszej setce jest ich dwadzieścia pięć, czyli co czwarta liczba, w piątej już siedemnaście, a w ostatniej setce pierwszego tysiąca czternaście. Ubytek nie jest gwałtowny i nigdy nie dochodzi do zera, ale jest stały, a powód widać wprost na sicie: każda kolejna liczba pierwsza wykreśla swoje wielokrotności, więc kandydatów ubywa z każdym przebiegiem, a im większa liczba, tym więcej ma szans na dzielnik mniejszy od swojego pierwiastka.
Rzednięcie nie znaczy jednak, że liczby pierwsze kiedyś się kończą, ani że układają się coraz równomierniej. Wśród liczb trzycyfrowych stoją obok siebie pary różniące się o dwa, na przykład 821 i 823 albo 881 i 883, a zaraz obok ciągną się odcinki bez ani jednej liczby pierwszej: między 887 a 907 nie ma żadnej. Pary bliźniacze i luki występują naprzemiennie przez całą oś i żadna prosta reguła nie mówi z góry, gdzie wypadnie następna liczba pierwsza.
Praktyczny wniosek dla arkusza jest krótszy niż teoria. Skoro w pierwszej setce liczb pierwszych jest dwadzieścia pięć, a pierwiastek z największej liczby czterocyfrowej jest mniejszy od stu, to test pierwszości dowolnej liczby czterocyfrowej wymaga najwyżej dwudziestu pięciu dzieleń. Ta sama tablica wystarcza więc do rozłożenia na czynniki każdej liczby, jaka pada w zadaniu; jak przeprowadzić taki rozkład krok po kroku, pokazuje kalkulator rozkładu na czynniki pierwsze.
| Zakres | Liczby pierwsze w zakresie | Łącznie od początku |
|---|---|---|
| 1 do 100 | 25 | 25 |
| 101 do 200 | 21 | 46 |
| 201 do 300 | 16 | 62 |
| 301 do 400 | 16 | 78 |
| 401 do 500 | 17 | 95 |
| 501 do 600 | 14 | 109 |
| 601 do 700 | 16 | 125 |
| 701 do 800 | 14 | 139 |
| 801 do 900 | 15 | 154 |
| 901 do 1000 | 14 | 168 |
Pułapki maturalne
Sprawdzanie dzielników aż do połowy liczby
Wystarczy dojść do pierwiastka kwadratowego z badanej liczby, a nie do jej połowy. Dla liczby 997 pierwiastek jest mniejszy od trzydziestu dwóch, więc testów jest jedenaście, a nie kilkaset. Bez tej obserwacji test pierwszości liczby trzycyfrowej nie mieści się w czasie, który daje arkusz.
Dwójka pomijana jako liczba parzysta
Dwójka jest liczbą pierwszą i jedyną parzystą liczbą pierwszą. Zdanie mówiące, że wszystkie liczby pierwsze są nieparzyste, jest fałszywe i w zadaniach typu prawda albo fałsz jest to najczęściej sprawdzane rozróżnienie w tym temacie.
Mylenie liczb pierwszych z liczbami względnie pierwszymi
Liczba pierwsza to cecha jednej liczby, a względna pierwszość to relacja między dwiema. Liczby osiem i dziewięć są względnie pierwsze, choć żadna z nich pierwsza nie jest. To dwa różne pojęcia i podstawienie jednego w miejsce drugiego zmienia treść zadania.
Najczęściej zadawane pytania
Sto sześćdziesiąt osiem. W pierwszej setce jest ich dwadzieścia pięć, w drugiej dwadzieścia jeden, a w ostatniej setce pierwszego tysiąca już tylko czternaście. Liczby pierwsze rzedną, im dalej w górę osi, ale nigdy się nie kończą.
Podziel ją przez kolejne liczby pierwsze nie większe od pierwiastka kwadratowego z niej. Jeśli żadna nie dzieli bez reszty, liczba jest pierwsza. Dla liczby 221 wystarczy dojść do czternastu i znaleźć dzielnik trzynaście, bo 221 to iloczyn trzynastu i siedemnastu.
Nie jest ani pierwsza, ani złożona. Liczba pierwsza ma dokładnie dwa dzielniki naturalne, a jedynka ma jeden. Wykluczenie jedynki jest tym, co pozwala mówić o jednoznacznym rozkładzie każdej liczby na czynniki pierwsze.
Dwadzieścia pięć: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 oraz 97. To jest ten zakres, który warto mieć w pamięci, bo pokrywa wszystkie dzielniki potrzebne do rozłożenia liczby czterocyfrowej.
Nie, jest ich nieskończenie wiele, co udowodnił Euklides ponad dwa tysiące lat temu. Dowód jest krótki: gdyby był ich skończony zbiór, iloczyn wszystkich powiększony o jeden nie dzieliłby się przez żadną z nich, a jakiś dzielnik pierwszy mieć musi.
Nie. Karta wzorów wydawana na egzaminie nie ma tablicy liczb pierwszych, więc rozkład na czynniki trzeba wykonać samodzielnie. To dlatego znajomość liczb pierwszych do stu jest realną oszczędnością czasu na arkuszu.