Liczby pierwsze i dzielniki
Ta część prezentacji skupia się na algorytmach związanych z liczbami pierwszymi i dzielnikami. Podstawowe algorytmy C++ przedstawione w tej sekcji są fundamentalne dla wielu zaawansowanych problemów programistycznych.
Zaprezentowano program znajdujący wszystkie dzielniki zadanej liczby n:
for(int i = 1; i <= n; i++)
if (n % i == 0)
cout << i;
Następnie przedstawiono zoptymalizowaną wersję tego algorytmu o złożoności O(√n):
for(int i = 1; i * i <= n; i++)
if (n % i == 0)
{
cout << i;
cout << n/i;
}
Highlight: Optymalizacja algorytmu znajdowania dzielników znacząco poprawia jego wydajność.
Przedstawiono również funkcję sprawdzającą, czy liczba jest pierwsza:
bool czy_pierwsza(int n)
{
for(int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
Vocabulary: Złożoność algorytmu - miara określająca, jak szybko rośnie czas wykonania algorytmu wraz ze wzrostem rozmiaru danych wejściowych.