Teoria liczb, Sito Eratostenesa i Systemy

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'

Cyfry liczby, NWD i NWW

Te trzy schematy wracają w niemal każdym arkuszu, zwykle jako element większego zadania: „ile liczb w pliku ma sumę cyfr podzielną przez 7”, „znajdź największy wspólny dzielnik wszystkich par”. Warto mieć je gotowe.

# CYFRY - wersja matematyczna (dziala na liczbie)
def suma_cyfr(n):
  s = 0
  while n > 0:
      s += n % 10       # ostatnia cyfra
      n //= 10          # obcinamy ja
  return s

# CYFRY - wersja tekstowa (czesto szybsza do napisania)
suma = sum(int(c) for c in str(n))
liczba_cyfr = len(str(n))
czy_palindrom = str(n) == str(n)[::-1]

# NWD - algorytm Euklidesa z reszta
def nwd(a, b):
  while b:
      a, b = b, a % b
  return a

# NWW wyprowadza sie z NWD - nie liczymy go osobno
def nww(a, b):
  return a * b // nwd(a, b)

Dlaczego Euklides jest szybki. Każdy krok co najmniej o połowę zmniejsza mniejszą z liczb, więc kroków jest rzędu

\log n

. Wersja z odejmowaniem zamiast reszty też działa, ale dla pary w rodzaju (1, 1000000) wykona milion obiegów — to gotowa odpowiedź na pytanie „którą wersję wybierzesz i dlaczego”.

Uwaga na zero. Pętla while n > 0 w sumie cyfr nie wykona się dla n = 0 i zwróci 0 — co akurat jest poprawne. Ale przy liczbach ujemnych trzeba użyć abs(n), inaczej pętla w ogóle nie ruszy.

NWW liczymy przez NWD, a nie przez szukanie wspólnej wielokrotności w pętli. Kolejność działań ma znaczenie: a * b // nwd(a, b) jest bezpieczne, bo Python nie ma ograniczenia rozmiaru liczb całkowitych.

Przegląd danych jednym przejściem

Najczęstsza struktura zadania z pliku: wczytaj dane, przejdź je raz i odpowiedz na kilka pytań naraz. Liczenie każdej odpowiedzi osobną pętlą działa, ale przy kilkudziesięciu tysiącach wierszy i pięciu podpunktach zaczyna być odczuwalne — a przy zagnieżdżonych pętlach wręcz uniemożliwia dokończenie zadania.

ile = 0
suma = 0
najwieksza = None
licznik = {}

for wartosc in dane:
  ile += 1
  suma += wartosc
  if najwieksza is None or wartosc > najwieksza:
      najwieksza = wartosc
  licznik[wartosc] = licznik.get(wartosc, 0) + 1

srednia = suma / ile
najczestsza = max(licznik, key=licznik.get)

Nie zaczynaj maksimum od zera. Gdy wszystkie dane są ujemne, wynik wyjdzie 0 — wartość, której w pliku w ogóle nie ma. Zacznij od None albo od pierwszego elementu.

Szukanie pary spełniającej warunek to jedyne miejsce, gdzie podwójna pętla bywa nieunikniona — ale zanim ją napiszesz, sprawdź, czy słownik albo posortowanie danych nie załatwią sprawy jednym przejściem. Przy dziesięciu tysiącach rekordów podwójna pętla to sto milionów obiegów.

Wypisz wynik od razu po policzeniu, a nie na końcu programu. Jeśli zabraknie czasu na ostatni podpunkt, wcześniejsze odpowiedzi i tak będą zapisane.

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 →