Wyznacza wszystkie dzielniki liczby naturalnej korzystając z symetrii – iteracja tylko do √n.
Dzielnik liczby n to taka liczba d, że n mod d = 0. Naiwny algorytm sprawdzałby wszystkie liczby od 1 do n, co dawałoby złożoność O(n).
Optymalizacja wykorzystuje fakt, że dzielniki pojawiają się parami: jeśli i dzieli n, to również n / i dzieli n. Wystarczy iterować tylko do √n i dla każdego znalezionego dzielnika i dodać do wyniku zarówno i, jak i n / i.
Przypadek szczególny: dla liczb kwadratowych (np. n = 36, i = 6) trzeba uważać, by nie dodać 6 dwa razy.
Na maturze: podstawowy algorytm pomocniczy. Wykorzystywany m.in. do znajdowania liczb pierwszych, doskonałych, zaprzyjaźnionych.
funkcja dzielniki(n): D ← pusta lista i ← 1 dopóki i * i ≤ n: jeżeli n mod i = 0: dodaj i do D // sprawdzamy czy nie dodajemy tego samego dzielnika dwa razy jeżeli i ≠ n div i: dodaj n div i do D i ← i + 1 posortuj D rosnąco zwróć D
def dzielniki(n):
wynik = []
i = 1
while i * i <= n:
if n % i == 0:
wynik.append(i)
# sprawdzamy czy n // i to nie ten sam dzielnik
if i != n // i:
wynik.append(n // i)
i += 1
return sorted(wynik)
# Przykład użycia
print(dzielniki(24))
# Wynik: [1, 2, 3, 4, 6, 8, 12, 24]
print(dzielniki(36))
# Wynik: [1, 2, 3, 4, 6, 9, 12, 18, 36]O(√n)O(√n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: