Liczby pierwsze i sito Eratostenesa w Pythonie i C++

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. Pierwsze są 2, 3, 5, 7, 11, 13 i tak dalej. Liczba 1 pierwsza nie jest (ma tylko jeden dzielnik), a 2 to jedyna parzysta liczba pierwsza. Liczby, które mają więcej dzielników, nazywamy złożonymi: 91 wygląda na pierwszą, ale 91 = 7 * 13.

Na tej stronie znajdziesz trzy algorytmy, które zawsze idą w parze: sprawdzanie, czy liczba jest pierwsza, sito Eratostenesa (wszystkie liczby pierwsze do granicy N) oraz rozkład na czynniki pierwsze. Każdy z nich przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź sito Eratostenesa krok po kroku

Sprawdzanie, czy liczba jest pierwsza

Najprostszy pomysł to sprawdzić wszystkie możliwe dzielniki od 2 do n - 1. Działa, ale robi dużo niepotrzebnej pracy. Kluczowa obserwacja: jeśli n = a * b, to jeden z czynników jest nie większy niż pierwiastek z n. Gdyby oba były większe, ich iloczyn przekroczyłby n. Wystarczy więc sprawdzać dzielniki d, dopóki d * d <= n. Dla n = 97 to tylko dzielniki od 2 do 9 zamiast od 2 do 96.

def czy_pierwsza(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True


for n in [1, 2, 9, 17, 91, 97]:
    print(n, czy_pierwsza(n))

1 False
2 True
9 False
17 True
91 False
97 True

Prześledźmy wywołanie czy_pierwsza(91):

Warunek d * d <= n jest lepszy niż d <= sqrt(n): nie wymaga liczb zmiennoprzecinkowych i nie grozi błędem zaokrąglenia przy dużych n.

Krokuj sprawdzanie dzielników do pierwiastka

Ta sama funkcja w C++ wypisuje liczby pierwsze do 30:

#include <iostream>
using namespace std;

bool czyPierwsza(int n) {
  if (n < 2) {
    return false;
  }
  for (int d = 2; d * d <= n; d++) {
    if (n % d == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  for (int n = 1; n <= 30; n++) {
    if (czyPierwsza(n)) {
      cout << n << endl;
    }
  }
  return 0;
}

2
3
5
7
11
13
17
19
23
29

Sito Eratostenesa: idea

Gdy potrzebujemy wszystkich liczb pierwszych do granicy N, sprawdzanie każdej liczby osobno jest marnotrawstwem. Eratostenes z Cyreny (III w. p.n.e.) zaproponował inny sposób: zamiast dzielić, wykreślamy.

1. Wypisz liczby od 2 do N. Na razie każda jest kandydatem na liczbę pierwszą.
2. Weź najmniejszą niewykreśloną liczbę p. Jest pierwsza.
3. Wykreśl wszystkie wielokrotności p, zaczynając od p * p.
4. Przejdź do następnej niewykreślonej liczby i powtarzaj, dopóki p * p <= N.
5. Wszystko, co zostało niewykreślone, jest pierwsze.

Dlaczego od p * p, a nie od 2 * p? Bo mniejsze wielokrotności, np. 3 * 2 albo 5 * 3, mają mniejszy czynnik pierwszy i zostały już wykreślone wcześniej. A dlaczego kończymy, gdy p * p > N? Bo każda liczba złożona do N ma czynnik nie większy niż pierwiastek z N, czyli została już wykreślona.

Sito Eratostenesa w Pythonie

W programie “wykreślenie” to po prostu zmiana wartości w liście z True na False. Indeks listy to liczba, a wartość mówi, czy ta liczba jest jeszcze kandydatem:

N = 50
pierwsza = [True] * (N + 1)
pierwsza[0] = pierwsza[1] = False
p = 2
while p * p <= N:
    if pierwsza[p]:
        for k in range(p * p, N + 1, p):
            pierwsza[k] = False
    p += 1

wynik = [i for i in range(N + 1) if pierwsza[i]]
print(wynik)
print("Ile:", len(wynik))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Ile: 15

Przebieg sita dla N = 50:

Część liczb wykreślamy kilka razy (np. 30 przy p = 2, 3 i 5), ale to tylko przypisanie False, więc nie szkodzi. Sito potrzebuje pamięci na listę długości N + 1, za to jest bardzo szybkie: liczby pierwsze do miliona znajduje w ułamku sekundy.

Sito Eratostenesa w C++

W C++ lista wartości logicznych to tablica bool. Ten program wypisuje liczby pierwsze do 50 i na końcu ich liczbę:

#include <iostream>
using namespace std;

int main() {
  const int N = 50;
  bool pierwsza[N + 1];
  for (int i = 0; i <= N; i++) {
    pierwsza[i] = true;
  }
  pierwsza[0] = false;
  pierwsza[1] = false;
  for (int p = 2; p * p <= N; p++) {
    if (pierwsza[p]) {
      for (int k = p * p; k <= N; k += p) {
        pierwsza[k] = false;
      }
    }
  }
  int ile = 0;
  for (int i = 2; i <= N; i++) {
    if (pierwsza[i]) {
      cout << i << " ";
      ile++;
    }
  }
  cout << endl;
  cout << "Ile: " << ile << endl;
  return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Ile: 15

Rozkład na czynniki pierwsze

Każdą liczbę większą od 1 da się zapisać jako iloczyn liczb pierwszych, i to tylko na jeden sposób (z dokładnością do kolejności). Algorytm dzieli n przez najmniejszy możliwy dzielnik tak długo, jak się da, a potem przechodzi do następnego:

n = 360
czynniki = []
d = 2
while d * d <= n:
    while n % d == 0:
        czynniki.append(d)
        n //= d
    d += 1
if n > 1:
    czynniki.append(n)
print(czynniki)

[2, 2, 2, 3, 3, 5]

Dla 360 pętla dzieli trzy razy przez 2 (360, 180, 90, 45), dwa razy przez 3 (45, 15, 5), a potem d = 3 rośnie do 4 i 4 * 4 > 5, więc pętla się kończy. Zostało n = 5 > 1, czyli ostatni czynnik. Dzięki temu, że dzielimy “do skutku”, do listy trafiają tylko liczby pierwsze: zanim d dojdzie do 4, wszystkie dwójki są już z n wyciągnięte.

Krokuj rozkład na czynniki pierwsze

W C++ wygodnie od razu wypisać rozkład w postaci iloczynu:

#include <iostream>
using namespace std;

int main() {
  int n = 360;
  cout << n << " =";
  bool pierwszy = true;
  for (int d = 2; d * d <= n; d++) {
    while (n % d == 0) {
      if (!pierwszy) {
        cout << " *";
      }
      cout << " " << d;
      pierwszy = false;
      n = n / d;
    }
  }
  if (n > 1) {
    if (!pierwszy) {
      cout << " *";
    }
    cout << " " << n;
  }
  cout << endl;
  return 0;
}

360 = 2 * 2 * 2 * 3 * 3 * 5

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Sprawdzanie, czy liczba jest pierwsza

Specyfikacja. Dane: liczba naturalna n. Wynik: TAK, gdy n jest liczbą pierwszą, w przeciwnym razie NIE.

Lista kroków:

1. Wczytaj liczbę n.
2. Jeśli n < 2, wypisz NIE i zakończ.
3. Ustaw d = 2.
4. Jeśli d · d > n, wypisz TAK i zakończ.
5. Jeśli n dzieli się przez d bez reszty, wypisz NIE i zakończ.
6. Zwiększ d o 1 i wróć do kroku 4.

Pseudokod:

wczytaj n
p ← n ≥ 2
d ← 2
dopóki p i d * d ≤ n wykonuj
  jeżeli n mod d = 0 to
    p ← fałsz
  d ← d + 1
jeżeli p to
  wypisz "TAK"
w przeciwnym razie
  wypisz "NIE"

Schemat blokowy:

Sito Eratostenesa

Specyfikacja. Dane: liczba naturalna n ≥ 2. Wynik: wszystkie liczby pierwsze od 2 do n.

Lista kroków:

1. Wczytaj n. Zaznacz wszystkie liczby od 2 do n jako kandydatów na liczby pierwsze.
2. Ustaw p = 2.
3. Jeśli p · p > n, przejdź do kroku 6.
4. Jeśli p jest zaznaczona, skreśl jej wielokrotności p · p, p · p + p, p · p + 2p i dalsze, aż do n.
5. Zwiększ p o 1 i wróć do kroku 3.
6. Wypisz liczby, które zostały zaznaczone, i zakończ.

Pseudokod:

wczytaj n
dla i = 2, 3, ..., n wykonuj
  T[i] ← prawda
p ← 2
dopóki p * p ≤ n wykonuj
  jeżeli T[p] to
    k ← p * p
    dopóki k ≤ n wykonuj
      T[k] ← fałsz
      k ← k + p
  p ← p + 1
dla i = 2, 3, ..., n wykonuj
  jeżeli T[i] to
    wypisz i

Schemat blokowy:

Rozkład liczby na czynniki pierwsze

Specyfikacja. Dane: liczba naturalna n ≥ 2. Wynik: czynniki pierwsze n od najmniejszego, z powtórzeniami.

Lista kroków:

1. Wczytaj n. Ustaw d = 2.
2. Jeśli d · d > n, przejdź do kroku 5.
3. Dopóki n dzieli się przez d bez reszty: wypisz d i zastąp n ilorazem n przez d.
4. Zwiększ d o 1 i wróć do kroku 2.
5. Jeśli n > 1, wypisz n (ostatni czynnik). Zakończ.

Pseudokod:

wczytaj n
d ← 2
dopóki d * d ≤ n wykonuj
  dopóki n mod d = 0 wykonuj
    wypisz d
    n ← n div d
  d ← d + 1
jeżeli n > 1 to
  wypisz n

Schemat blokowy:

Najczęstsze błędy

• Uznanie 1 za liczbę pierwszą. Bez warunku n < 2 funkcja zwraca True dla 1 (i dla 0), bo pętla w ogóle się nie wykona. W sicie trzeba ręcznie ustawić pierwsza[0] i pierwsza[1] na False.
• Zwracanie True za wcześnie. else: return True wewnątrz pętli kończy funkcję po sprawdzeniu pierwszego dzielnika: 9 % 2 = 1, więc 9 wyszłaby “pierwsza”. Odpowiedź “pierwsza” wolno dać dopiero po całej pętli.
• Zły warunek końca. d * d < n zamiast d * d <= n przepuszcza kwadraty liczb pierwszych: 25 i 49 wyszłyby pierwsze.
• Za krótka tablica w sicie. Dla liczb do N potrzeba N + 1 elementów, bo indeksy zaczynają się od 0. Tablica bool pierwsza[N] w C++ nie ma miejsca na N.
• Rozkład bez reszty na końcu. Bez if n > 1 rozkład 14 zwróci tylko [2], bo czynnik 7 jest większy od pierwiastka z tego, co zostało.

Ćwicz w przeglądarce

W temacie “Liczby pierwsze i sito Eratostenesa” kursu Algorytmy z podstawy programowej czekają trzy przykłady do krokowania i zadania, które sprawdzają się automatycznie po uruchomieniu:

• ile jest liczb pierwszych do 100,
• sprawdź, czy liczba jest pierwsza,
• liczby pierwsze bliźniacze do 100.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości p, k i listy pierwsza, więc widać, jak kolejne liczby znikają z sita. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Podzielność łączy się bezpośrednio z algorytmem Euklidesa, a pętla “dziel, dopóki się da” wraca przy sumie cyfr liczby. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Liczby pierwsze to dobry temat na porównanie dwóch podejść do tego samego problemu: uczniowie piszą najpierw sprawdzanie dzielników, potem sito, i mogą policzyć, ile dzieleń oszczędza warunek d * d <= n. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.