Zadania z liczb pierwszych wracają w arkuszach w dwóch odsłonach: sprawdź, czy jedna duża liczba jest pierwsza, oraz wypisz wszystkie liczby pierwsze z przedziału. W obu punkty za efektywność zależą od tego samego chwytu — pętla idzie tylko do pierwiastka z badanej liczby, a przy całym przedziale zamiast sprawdzania liczba po liczbie wchodzi sito. Ten sam pierwiastek ogranicza rozkład na czynniki pierwsze. Na zajęciach zaczynamy od wersji nieoptymalnej, czyli pętli do n. Dopiero potem pokazujemy, że wystarczy iść do pierwiastka — i przy okazji tłumaczymy, czym w ogóle jest złożoność obliczeniowa.

Optymalizacja czasu: Magia pierwiastka kwadratowego

Kiedy CKE każe sprawdzić, czy ogromna liczba (np. z rzędu miliardów) jest liczbą pierwszą, naiwne sprawdzenie wszystkich dzielników w pętli od 2 do $n-1$ to samobójstwo. Twój program przekroczy limit czasu (zazwyczaj 1 sekunda), a punkty za efektywność po prostu przepadną.

💡 Złota zasada maturalna:

Dzielniki zawsze występują w parach. Jeśli liczba $n$ dzieli się przez $a$ , to dzieli się również przez $b$ , gdzie $a \cdot b = n$ . Jeden z tych dzielników z pewnością jest mniejszy lub równy $\sqrt{n}$ .

Wniosek? Pętlę szukającą dzielników wystarczy uruchomić tylko do pierwiastka kwadratowego z badanej liczby! Oszczędzasz miliony niepotrzebnych iteracji.

Sito Eratostenesa – Fabryka liczb pierwszych

Gdy musisz wygenerować wszystkie liczby pierwsze w szerokim przedziale (np. od 1 do miliona), sprawdzanie każdej liczby osobną funkcją to strata czasu. Do gry wkracza starożytny, ale potężny algorytm – Sito Eratostenesa.

Jak działa Sito?

Tworzymy długą listę wartości True, zakładając wstępnie, że wszystkie liczby są pierwsze.
Bierzemy pierwszą prawdziwą liczbę pierwszą (2) i "wykreślamy" (zmieniamy na False) wszystkie jej wielokrotności.
Przechodzimy do kolejnej niewykreślonej liczby (3) i powtarzamy proces.
Algorytm możemy bezpiecznie zatrzymać, gdy dojdziemy do pierwiastka z górnego zakresu!

Pythonowa implementacja Sita:

def sito_eratostenesa(n):
  # Tablica wartości True (indeksy odpowiadają liczbom)
  pierwsze = [True] * (n + 1)
  pierwsze[0] = pierwsze[1] = False 
  
  # Przeszukujemy tylko do pierwiastka z n!
  for i in range(2, int(n**0.5) + 1):
      if pierwsze[i]: 
          # Wykreślamy wielokrotności zaczynając od i*i
          for j in range(i * i, n + 1, i):
              pierwsze[j] = False
              
  # Zwracamy listę zachowanych liczb
  return [x for x in range(n + 1) if pierwsze[x]]

print(sito_eratostenesa(30)) 
# Wynik: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Rozkład liczby na czynniki pierwsze

Każdą liczbę złożoną można zapisać jako unikalny iloczyn liczb pierwszych. Ten algorytm jest sercem zadań z NWD (Największym Wspólnym Dzielnikiem) i skracaniem ułamków.

Zamiast kombinować i najpierw generować liczby pierwsze, robimy to sprytniej w czasie $O(\sqrt{n})$ – po prostu dzielimy liczbę przez najmniejszy możliwy dzielnik dopóki się da, a gdy się nie da, zwiększamy dzielnik.

Zadanie

Śledzenie algorytmu (Dry run):

Przeanalizuj proces rozkładu na czynniki pierwsze dla liczby $n = 84$ . Zapisz, jakie wartości lądują na liście czynników w poszczególnych krokach pętli.

💡 Pokaż rozwiązanie krok po kroku▼

1
Krok 1: Dzielimy przez najmniejszy dzielnik $d = 2$
Liczba 84 jest parzysta. Wykonujemy $84 : 2 = 42$ . Dopisujemy 2 do listy.
Wynik (42) też dzieli się przez 2. Wykonujemy $42 : 2 = 21$ . Dopisujemy drugą 2 do listy.
21 nie dzieli się przez 2. Zwiększamy wartość naszego potencjalnego dzielnika.
2
Krok 2: Sprawdzamy kolejne dzielniki ( $d = 3$ )
Sprawdzamy obecne $n = 21$ . Dzieli się przez 3! Wykonujemy $21 : 3 = 7$ . Dopisujemy 3 do listy.
Liczba 7 nie dzieli się przez 3 (ani 4, 5, 6...). Zwiększamy dzielnik aż dobijemy do 7.

Krok 3: Ostatni dzielnik i wynik

Obecne $n = 7$ dzieli się przez $d = 7$ . Wynik to 1. Dopisujemy 7 do listy. Ponieważ osiągnęliśmy 1, pętla się kończy.

# Ostateczny kod tego algorytmu wygląda tak:
def rozklad_na_czynniki(n):
  czynniki = []
  d = 2
  while d * d <= n:
      while n % d == 0:
          czynniki.append(d)
          n //= d
      d += 1
  if n > 1:
      czynniki.append(n)
  return czynniki

Systemy liczbowe (Pythonowy Cheat-sheet)

Na maturze non-stop przeliczasz wartości między systemem binarnym, dziesiętnym i szesnastkowym. Oczywiście, możesz ręcznie pisać algorytm Hornera, ale Python posiada genialne, wbudowane narzędzia, które załatwiają to w jednej linijce!

➡️ Na dziesiętny

Używaj potężnej funkcji int("string", podstawa).

int("1010", 2) # Zwróci 10
int("FF", 16) # Zwróci 255

🔢 Na binarny

Używaj funkcji bin(liczba). Zwraca ona string z przedrostkiem '0b'.

bin(10) # '0b1010'
bin(10)[2:] # Odcina '0b'

🔤 Na szesnastkowy

Używaj funkcji hex(liczba). Zwraca string z przedrostkiem '0x'.

hex(255) # '0xff'
hex(255)[2:].upper() # 'FF'

Przeczytaj też

Algorytmy, które realnie przydają się na maturze

Zestaw algorytmów wracających w arkuszach, z gotowym kodem i wyjaśnieniem, kiedy który wybrać.

Uczysz się w technikum informatycznym? Prowadzimy też przygotowanie do kwalifikacji INF.02, INF.03 i INF.04. Zobacz egzaminy zawodowe →

Teoria liczb, Sito Eratostenesa i Systemy