Teoria liczb, Sito Eratostenesa i Systemy - Pewniak Maturalny 2026

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'