Liczby pierwsze i sito Eratostenesa
Informatyka, klasa 6 · Algorytmy
Najważniejsze w skrócie
Liczba pierwsza ma dokładnie dwa różne dzielniki: 1 i samą siebie, np. 2, 3, 5, 7, 11, 13. Liczba większa od 1, która ma więcej dzielników, jest złożona, np. 12 = 2 · 6. Liczba 1 nie jest ani pierwsza, ani złożona, bo ma tylko jeden dzielnik.
Liczba 2 to jedyna parzysta liczba pierwsza — każda inna liczba parzysta dzieli się przez 2. Żeby sprawdzić, czy n jest pierwsza, wystarczy szukać dzielników od 2 do pierwiastka z n. Dla 97 sprawdzamy 2, 3, 5 i 7, bo 10 · 10 = 100 to już więcej niż 97; żadna z nich nie dzieli 97, więc 97 jest pierwsza.
Sito Eratostenesa znajduje wszystkie liczby pierwsze do zadanego n. Wypisujemy liczby od 2, bierzemy najmniejszą nieskreśloną i skreślamy wszystkie jej wielokrotności, potem powtarzamy to dla następnej. Do 100 wystarczy skreślić wielokrotności 2, 3, 5 i 7 — zostaje 25 liczb pierwszych.
Ważne daty
- 2 — najmniejsza i jedyna parzysta liczba pierwsza
- 1 — ani pierwsza, ani złożona
- 25 — tyle jest liczb pierwszych do 100
- √n — dzielników szukamy tylko do pierwiastka z n
- III w. p.n.e. — Eratostenes z Cyreny opisuje swoje sito
Ważne postacie
- Eratostenes — grecki uczony, autor sita; zmierzył też obwód Ziemi
- Euklides — udowodnił, że liczb pierwszych jest nieskończenie wiele
- Liczba 2 — jedyna parzysta liczba pierwsza
- Liczba złożona — ma więcej niż dwa dzielniki, np. 15 = 3 · 5
Pojęcia
- Co to liczba pierwsza?
- Liczba większa od 1, która dzieli się tylko przez 1 i przez samą siebie.
- Co to liczba złożona?
- Liczba większa od 1, która ma więcej niż dwa dzielniki, np. 15 = 3 · 5.
- Czy 1 jest liczbą pierwszą?
- Nie — ma tylko jeden dzielnik.
- Jaka jest jedyna parzysta liczba pierwsza?
- 2.
- Wymień liczby pierwsze mniejsze od 20.
- 2, 3, 5, 7, 11, 13, 17, 19.
- Do jakiej liczby szukamy dzielników, sprawdzając, czy n jest pierwsza?
- Do pierwiastka z n — dzielniki występują w parach i jeden z pary jest zawsze nie większy od pierwiastka.
- Kto wymyślił sito do szukania liczb pierwszych?
- Eratostenes z Cyreny, grecki uczony z III wieku p.n.e.
- Co skreślamy w sicie Eratostenesa?
- Wielokrotności kolejnych nieskreślonych liczb.
- Kiedy można zakończyć skreślanie w sicie do n?
- Gdy kwadrat kolejnej nieskreślonej liczby przekroczy n.
- Ile jest liczb pierwszych do 100?
- 25.
- Czy 91 jest liczbą pierwszą?
- Nie, bo 91 = 7 · 13.
- Rozłóż 84 na czynniki pierwsze.
- 84 = 2 · 2 · 3 · 7.
Sprawdź się
1. Liczba pierwsza ma:
- dokładnie jeden dzielnik, czyli siebie
- dokładnie dwa dzielniki
- zawsze nieparzystą liczbę cyfr
- więcej niż dwa różne dzielniki
Pokaż odpowiedź
B. dokładnie dwa dzielniki — Te dwa dzielniki to 1 i sama liczba — innych nie ma, np. 7 dzieli się tylko przez 1 i 7.
2. Liczba złożona to liczba większa od 1, która:
- ma więcej niż dwa dzielniki
- ma dokładnie dwa dzielniki
- kończy się cyfrą zero lub pięć
- nie dzieli się przez żadną liczbę
Pokaż odpowiedź
A. ma więcej niż dwa dzielniki — Na przykład 12 dzieli się przez 1, 2, 3, 4, 6 i 12 — to dużo więcej niż dwa dzielniki.
3. W sicie Eratostenesa po pozostawieniu liczby 3 skreślamy:
- wszystkie liczby nieparzyste
- wszystkie wielokrotności 3
- liczby kończące się cyfrą 3
- tylko liczby 6 i 9
Pokaż odpowiedź
B. wszystkie wielokrotności 3 — Wielokrotności 3 mają dzielnik 3, więc nie mogą być pierwsze; sama 3 zostaje.
4. Kto wymyślił sito do wyszukiwania liczb pierwszych?
- Euklides
- Pitagoras
- Eratostenes
- Archimedes z Syrakuz
Pokaż odpowiedź
C. Eratostenes — Eratostenes z Cyreny opisał tę metodę w III wieku p.n.e., stąd nazwa „sito Eratostenesa”.
5. W sicie Eratostenesa kolejną liczbę pierwszą rozpoznajemy po tym, że:
- jest liczbą nieparzystą
- kończy się cyfrą 1, 3, 7 lub 9
- jest dwa razy większa od poprzedniej
- nie została wcześniej skreślona
Pokaż odpowiedź
D. nie została wcześniej skreślona — Liczba nieskreślona nie jest wielokrotnością żadnej mniejszej liczby pierwszej, więc sama jest pierwsza.
Więcej pytań — razem 50 fiszek, pytań i zdań prawda/fałsz — czeka w ćwiczeniach.
▶ Ćwicz ten temat fiszki, quiz i prawda/fałsz — z wynikiem i powtórkami