Jak znaleźć wszystkie dzielniki liczby – sprawdzamy tylko do pierwiastka i dorzucamy pary.
Dzielnik liczby n to taka liczba d, przez którą n dzieli się bez reszty (czyli n mod d = 0). Na przykład dzielniki 24 to 1, 2, 3, 4, 6, 8, 12, 24. Każda liczba ma co najmniej dwa dzielniki: 1 oraz samą siebie (a liczba, która ma dokładnie dwa, to liczba pierwsza).
Jak to policzyć najprościej? Sprawdzamy po kolei liczby od 1 do n i za każdym razem patrzymy, czy dzieli n. To działa, ale dla dużych liczb jest wolne – robimy n sprawdzeń.
Szybszy sposób – pary dzielników. Dzielniki chodzą parami: jeśli i dzieli n, to n / i też jest dzielnikiem. Na przykład dla 24: 2 i 12, 3 i 8, 4 i 6. Jeden z każdej pary jest zawsze ≤ √n. Wystarczy więc sprawdzić i tylko do pierwiastka z n, a dla każdego trafionego i dopisać od razu dwa dzielniki: i oraz n / i. Tak z n sprawdzeń robi się tylko około √n.
Uwaga na liczby kwadratowe. Gdy n jest kwadratem (np. 36 = 6 · 6), to dla i = 6 mamy n / i = 6 – ten sam dzielnik. Trzeba go wtedy dopisać tylko raz, inaczej 6 pojawi się podwójnie.
Na maturze: to podstawowy klocek wielu zadań – liczenie, ile liczba ma dzielników, sprawdzanie liczb pierwszych i doskonałych, a także rozkład na czynniki pierwsze.
Prześledź krok po kroku, jak znajdujemy wszystkie dzielniki liczby. Sprawdzamy i = 1, 2, 3, … tylko do √n. Gdy i dzieli n bez reszty, dorzucamy od razu parę: i oraz n / i (dla pierwiastka liczby kwadratowej tylko raz, żeby nie liczyć go podwójnie).
Naciśnij „Krok", aby sprawdzić pierwsze i, albo „Auto".
funkcja dzielniki(n): D ← pusta lista i ← 1 dopóki i * i ≤ n: jeżeli n mod i = 0: dodaj i do D jeżeli i ≠ n div i: // nie dodawaj pierwiastka dwa razy dodaj n div i do D i ← i + 1 posortuj D rosnąco zwróć D
def dzielniki(n):
"""Zwraca posortowaną listę wszystkich dzielników liczby n."""
wynik = []
i = 1
while i * i <= n:
if n % i == 0:
wynik.append(i)
if i != n // i: # nie dodawaj pierwiastka dwa razy
wynik.append(n // i)
i += 1
return sorted(wynik)
# Przykłady 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]#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> dzielniki(int n) {
vector<int> wynik;
for (int i = 1; (long long)i * i <= n; i++) {
if (n % i == 0) {
wynik.push_back(i);
if (i != n / i) { // nie dodawaj pierwiastka dwa razy
wynik.push_back(n / i);
}
}
}
sort(wynik.begin(), wynik.end());
return wynik;
}
int main() {
for (int d : dzielniki(24)) cout << d << " ";
// Wynik: 1 2 3 4 6 8 12 24
}To liczba, przez którą nasza liczba dzieli się bez reszty. Na przykład 3 jest dzielnikiem 12, bo 12 : 3 = 4 i nic nie zostaje.
Bo dzielniki chodzą w parach i oraz n / i, a mniejszy z pary jest zawsze ≤ √n. Sprawdzając do pierwiastka, dla każdego małego dzielnika od razu poznajemy jego większego partnera.
Dotyczy liczb kwadratowych. Gdy i jest pierwiastkiem n (np. 6 dla 36), to i oraz n / i to ta sama liczba – trzeba ją dopisać tylko raz.
Przy sprawdzaniu, czy liczba jest pierwsza, przy liczbach doskonałych, a także jako pomoc przy rozkładzie na czynniki pierwsze i w wielu zadaniach maturalnych o liczbach.
Wypisz wszystkie dzielniki i policz, ile ich jest. Kliknij Sprawdź.
Liczba 6 ma dzielniki `1, 2, 3, ` – jest ich . Liczba 10 ma dzielniki `1, 2, 5, `.
Uzupełnij, ile dzielników ma każda liczba:
| Liczba | Ile dzielników |
|---|---|
| 7 | |
| 12 | |
| 16 |
Sprawdzając dzielniki, iterujemy i tylko dopóki i * i jest od n, a dla trafionego i dopisujemy też dzielnik .
O(√n)O(√n)Pętla zwiększa i tylko do pierwiastka z n (warunek i · i ≤ n), więc liczba sprawdzeń rośnie jak √n – stąd czas O(√n). Pamięć to O(√n), bo w najgorszym razie zapisujemy wszystkie znalezione dzielniki, a liczba dzielników nie przekracza tego rzędu.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: