Sito Eratostenesa, algorytm Euklidesa, rozkład na czynniki, systemy liczbowe
Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 10/30
1. Sito Eratostenesa — wyznaczanie liczb pierwszych
Aby znaleźć wszystkie liczby pierwsze do n, zamiast sprawdzać podzielność każdej liczby osobno (co byłoby wolne), "wykreślamy" wielokrotności każdej znalezionej liczby pierwszej. Złożoność tego algorytmu to O(n log log n) — praktycznie niemal liniowa.
def sito_eratostenesa(n):
czy_pierwsza = [True] * (n + 1)
czy_pierwsza[0] = czy_pierwsza[1] = Falsefor i in range(2, int(n**0.5) + 1):
if czy_pierwsza[i]:
for wielokrotnosc in range(i*i, n + 1, i):
czy_pierwsza[wielokrotnosc] = Falsereturn [i for i in range(n + 1) if czy_pierwsza[i]]
2. Algorytm Euklidesa — NWD i NWW
Największy wspólny dzielnik dwóch liczb można wyznaczyć bardzo szybko, korzystając z faktu, że NWD(a, b) = NWD(b, a mod b).
def nwd_rekurencyjnie(a, b):
if b == 0:
return a
return nwd_rekurencyjnie(b, a % b)
def nwd_iteracyjnie(a, b):
while b != 0:
a, b = b, a % b
return a
def nww(a, b):
return a * b // nwd_iteracyjnie(a, b)
Dlaczego to działa tak szybko?
Algorytm Euklidesa ma złożoność O(log(min(a,b))) — to jedno z najstarszych (starożytna Grecja!) i wciąż najefektywniejszych narzędzi teorii liczb, wykorzystywane m.in. w kryptografii RSA (Blok 26).
3. Rozkład liczby na czynniki pierwsze
def czynniki_pierwsze(n):
wynik = []
dzielnik = 2
while dzielnik * dzielnik <= n:
while n % dzielnik == 0:
wynik.append(dzielnik)
n //= dzielnik
dzielnik += 1
if n > 1:
wynik.append(n)
return wynik
# czynniki_pierwsze(360) -> [2, 2, 2, 3, 3, 5]
4. Zamiana systemów liczbowych
Zamiana z systemu dziesiętnego na dowolny inny polega na wielokrotnym dzieleniu z resztą przez podstawę systemu docelowego i odczytaniu reszt w kolejności odwrotnej.
def dziesietny_na_system(n, podstawa):
if n == 0:
return"0"
cyfry = "0123456789ABCDEF"
wynik = ""while n > 0:
wynik = cyfry[n % podstawa] + wynik
n //= podstawa
return wynik
# dziesietny_na_system(156, 2) -> "10011100" (binarnie)# dziesietny_na_system(156, 16) -> "9C" (szesnastkowo)# wbudowane odpowiedniki: bin(156), oct(156), hex(156)
5. Ćwiczenia praktyczne
Ćwiczenie 1 — liczby względnie pierwsze
Napisz funkcję sprawdzającą, czy dwie liczby są względnie pierwsze (czyli NWD(a,b) = 1), a następnie wypisz wszystkie liczby od 1 do 20 względnie pierwsze z 20.
Ćwiczenie 2 — funkcja odwrotna
Napisz funkcję system_na_dziesietny(tekst, podstawa), która zamieni liczbę zapisaną w dowolnym systemie (jako string) z powrotem na system dziesiętny.
def system_na_dziesietny(tekst, podstawa):
cyfry = "0123456789ABCDEF"
wynik = 0
for znak in tekst:
wynik = wynik * podstawa + cyfry.index(znak)
return wynik
Sprawdź wiedzę
1. Jaka jest złożoność sita Eratostenesa?
2. Na jakiej zależności opiera się algorytm Euklidesa?
3. Jak wyznacza się cyfry liczby przy zamianie na inny system liczbowy?