Pierwszym z elementów będą liczby rzeczywiste. Napiszemy program, który wczytuje kwotę pieniędzy i oprocentowanie lokaty w skali roku i wypisze kwotę, jaka po roku będzie znajdować się na lokacie. Do rozwiązania tego zadania użyjemy typu rzeczywistego double. Liczby rzeczywiste w C++ zapisujemy w formie ułamków dziesiętnych, a część całkowitą i ułamkową rozdzielamy kropką dziesiętną (a nie przecinkiem!).

#include <iostream>

using namespace std;
 
int main() {
    double kwota, procent;
    cin >> kwota >> procent;
    cout << kwota + kwota * procent / 100.0 << endl;
}

Dla kwoty 100 zł i oprocentowania 4% wynikiem programu jest 104 zł, a dla kwoty 123 zł i oprocentowania 3.5% wynik to 127.305 zł.

Przy wypisywaniu liczb rzeczywistych dobrze jest określić, ile cyfr po kropce chcemy wypisać. Liczba zostanie wtedy zaokrąglona do tylu cyfr po kropce. W tym celu trzeba dołączyć plik nagłówkowy iomanip, służący do manipulowania wyjściem. Funkcja setprecision ustawia liczbę cyfr dziesiętnych do wypisania – w przypadku kwoty w złotówkach będą to dwie cyfry po kropce. Jeśli nie podamy liczby cyfr, które chcemy, by program wypisał po przecinku, domyślnie wypisywane jest maksymalnie 6 cyfr, wliczając cyfry przed kropką dziesiętną, a jeśli przy tym liczba przekroczy 6 cyfr, zostanie wypisana w tzw. notacji naukowej, której znaczenia tutaj nie będziemy wyjaśniać.

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    double kwota, procent;
    cin >> kwota >> procent;
    cout << setprecision(2) << fixed;
    cout << kwota + kwota * procent / 100.0 << endl;
}

Uwaga: Zwracamy uwagę na konieczność użycia słówka fixed. Bez niego liczba podana w funkcji setprecision będzie traktowana jako łączna liczba cyfr do wypisania, wraz z cyframi przed kropką.

Na liczbach rzeczywistych można wykonywać standardowe działania dodawania, odejmowania, mnożenia oraz dzielenia "/". Oprócz tego dostępnych jest wiele funkcji matematycznych, takich jak pierwiastek kwadratowy (sqrt), podnoszenie do danej potęgi (pow(liczba,wykładnik)), funkcje trygonometryczne (sin, cos, tan), wartość bezwzględna (abs), całość z liczby (floor), zaokrąglenie do najbliższej liczby całkowitej (round), logarytm dwójkowy, dziesiętny i naturalny (log2, log10, log) itd. Wszystkie te funkcje są dostępne w pliku nagłówkowym cmath.

Jako skromną ilustrację tych możliwości języka C++ napiszmy program, który oblicza długość przeciwprostokątnej trójkąta prostokątnego na podstawie długości przyprostokątnych z twierdzenia Pitagorasa i wypisuje wynik z pięcioma cyframi po kropce. Pamiętajmy, że oprócz cmath wciąż musimy dołączyć plik nagłówkowy iomanip.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() {
    double a, b;
    cin >> a >> b;
    cout << setprecision(5) << fixed;
    cout << sqrt(a * a + b * b) << endl;
}

W komputerze nie ma możliwości przechowywać nieskończenie wielu cyfr po przecinku, dlatego każda liczba rzeczywista jest pamiętana z pewnym przybliżeniem – a zatem najmniej ważne cyfry w zapisie mogą zostać pominięte. W obliczenia na liczbach rzeczywistych wkradają się zatem bardzo drobne błędy, które wraz z wykonywaniem kolejnych obliczeń mogą się nawarstwiać. Dobre rozumienie reprezentacji liczb rzeczywistych w komputerze, zakresów typów rzeczywistych oraz błędów przybliżeń wymaga pewnego doświadczenia. Dlatego na początkowym etapie nauki programowania, na którym się obecnie znajdujesz, mamy dla Ciebie bardzo prostą radę: używaj liczb rzeczywistych w swoich programach tylko, jeśli są one konieczne.

Czasem dane do programu występują w naturalny sposób w formie tabelki. Wtedy do ich przechowywania można użyć tablicy dwuwymiarowej. Taką tablicę deklaruje się podobnie do tablicy jednowymiarowej:

int t[100][100];

Elementy tej tablicy wyglądają tak: \(t[i][j]\) dla \(i\) i \(j\) od 0 do 99 włącznie.

Jako przykład rozważmy wyniki sprawdzianu w danej klasie: dla każdego ucznia wiemy, ile punktów uzyskał za każde zadanie. Powiedzmy, że mamy \(n\) uczniów i \(m\) zadań. Dla \(n=3\) i \(m=4\) dane do programu wyglądają tak:

3 4
2 0 5 1
3 3 1 4
0 0 5 5

Wtedy te dane możemy umieścić w tablicy dwuwymiarowej za pomocą zagnieżdżonych pętli for:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int spr[n][m];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> spr[i][j];
}

Czyli dla tych danych mamy \(spr[0][0]=2\), \(spr[0][1]=0\), \(spr[0][2]=5\), \(spr[0][3]=1\), dalej \(spr[1][0]=3\), \(spr[1][1]=3\) itd.

Gdy już wczytamy takie dane, możemy dla każdego z uczniów obliczyć sumę punktów ze sprawdzianu:

    for (int i = 0; i < n; ++i) {
        int suma = 0;
        for (int j = 0; j < m; ++j)
            suma += spr[i][j];
        cout << suma << endl;
    }

Podobnie, dla każdego z zadań możemy obliczyć średni wynik uczniów z tego zadania:

    cout << endl;
    cout << setprecision(2) << fixed;
    for (int i = 0; i < m; ++i) {
        int suma = 0;
        for (int j = 0; j < n; ++j)
            suma += spr[j][i];
        cout << double(suma) / n << endl;
    }

Wynikiem tego programu dla danych powyżej jest

8
11
10

1.67
1.00
3.67
3.33

W C++ podobnie jak tablice dwuwymiarowe zachowują się tablice napisów, czyli tablice elementów typu string. Tutaj również mamy podwójne indeksy służące do dostępu do pojedynczych znaków napisów.

Zilustrujemy to sympatycznym przykładem szachowym. Wieża w szachach to figura, która atakuje wszystkie pola znajdujące się w tym samym wierszu i w tej samej kolumnie co ona. Napiszemy program, który wczyta zawartość szachownicy \(n \times n\), na której znajduje się pewna liczba wież, i wypisze TAK, jeśli jakiekolwiek dwie wieże na tej szachownicy atakują się, a NIE w przeciwnym przypadku. Przykładowo, dla danych:

4
..W.
W...
....
...W

odpowiedzią jest NIE, a dla danych:

4
..W.
W...
..W.
...W

odpowiedź brzmi TAK.

Oto program. Zauważ, że napisy wczytuje się inaczej niż tablice (prościej).

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n;
    cin >> n;
    string szach[n];
    for (int i = 0; i < n; ++i)
        cin >> szach[i];
    bool atak = false;

    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[i][j] == 'W')
                ++ile;
        if (ile > 1)
            atak = true;
    }

    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[j][i] == 'W')
                ++ile;
        if (ile > 1)
            atak = true;
    }

    if (atak)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

W programie tym nie udało nam się uniknąć przykrego przeklejania dłuższego fragmentu kodu. Jest to zjawisko niepożądane, gdyż łatwo w ten sposób wprowadzić do programu jakąś usterkę: albo zapominając zmienić coś w trakcie przeklejania, albo też później, gdy poprawiamy pierwszy fragment programu, a zapomnimy to samo poprawić w drugim. Aby tego uniknąć, możemy tu napisać funkcję sprawdzającą, czy w którymś wierszu jakieś dwie wieże atakują się. Następnie możemy wywołać tę funkcję dwukrotnie, a między jej wywołaniami odbić całą szachownicę symetrycznie względem przekątnej. Szczegóły analizy tego programu pozostawiamy uczestnikom kursu.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
string szach[1000];

bool czy_szach() {
    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[i][j] == 'W')
                ++ile;
        if (ile > 1)
            return true;
    }
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> szach[i];
    bool atak = czy_szach();

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            swap(szach[i][j], szach[j][i]);

    atak = atak || czy_szach();

    if (atak)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

do
    instrukcja;
while (warunek);

#include <iostream>
using namespace std;

int main() {
    int suma = 0;
    do {
        int a;
        cin >> a;
        suma += a;
    } while (a != 0);
    cout << suma << endl;
}

Na ziemi wytyczono niewielkie koło, na jego obwodzie umieszczono trzy kołki. Na jeden z nich nałożono płaskie klocki w kształcie pierścieni. Każdy pierścień ma inną średnicę. Pierścienie zostały nałożone w kolejności od największego (na spodzie) do najmniejszego (na wierzchu). Pierścienie można przekładać z kołka na kołek, ale tylko pojedynczo, i nie wolno kłaść większego pierścienia na mniejszy. Przy tych ograniczeniach należy przełożyć wszystkie pierścienie na inny kołek (którykolwiek).

Algorytm

1. Usiądź wewnątrz koła.
2. Przenieś najmniejszy pierścień o jeden kołek w prawo.
3. Dopóki wszystkie pierścienie nie znajdą się na jednym kołku: 3.1 Wykonaj jedyne możliwe przeniesienie bez ruszania najmniejszego pierścienia; innymi słowy, przenieś mniejszy z pierścieni znajdujących się na wierzchach kołków niezawierających najmniejszego pierścienia na drugi z tych kołków. 3.2 Przenieś najmniejszy pierścień o jeden kołek w prawo.

Załóżmy, że mamy do przeniesienia \(n > 0\) pierścieni. Przyjmijmy, że jeden ruch w naszym algorytmie polega na przełożeniu jednego pierścienia pomiędzy wieżami. Ilu ruchów potrzebuje nasz algorytm do przełożenia wszystkich pierścieni? Oznaczmy liczbę wszystkich ruchów przez \(T(n)\). Jeśli mamy tylko jeden pierścień (\(n = 1\)), wystarczy tylko 1 ruch. Jeżeli \(n > 1\), to musimy najpierw przenieść \(n-1\) najmniejszych pierścieni w celu uwolnienia największego pierścienia. Na to potrzeba \(T(n-1)\) ruchów. Potem w jednym ruchu przenosimy największy pierścień, a na koniec musimy przenieść na wieżę z największym pierścieniem \(n-1\) najmniejszych pierścieni – znowu \(T(n-1)\) ruchów. Zatem liczbę ruchów wykonywanych przez nasz algorytm można wyrazić następującym układem równań:

\(T(1) = 1\); \(T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) +1\).

Nietrudno wykazać, że \(T(n) = 2^n - 1\). Dlaczego?

\(T(1) = 2^1 - 1 = 2 - 1 = 1\);

\(T(n) = 2 \cdot (2^{n-1} - 1) + 1 = 2\cdot 2^{n-1} - 2 + 1 = 2^n - 1\).

Legenda głosi, że mnisi w Tybecie mają do przełożenia 64 pierścienie i gdy je wszystkie przełożą, nastąpi koniec świata. Jeśli wykonanie jednego ruchu zabiera sekundę, to przełożenie wszystkich pierścieni zajęłoby \(2^{64}-1 = 18\,446\,744\,073\,709\,551\,615\) (ponad 18 trylionów) sekund, czyli około 584 miliardów lat.

Załóżmy teraz, że dany jest numer ruchu \(r\), \(0 \le r \le 2^n - 1\). Jak wygląda konfiguracja pierścieni na wieżach zaraz po wykonaniu ruchu o numerze \(r\)? Oczywiście moglibyśmy poprosić mnichów o wykonanie \(r\) ruchów naszego algorytmu i dostać pożądaną konfigurację, ale na odpowiedź moglibyśmy się nie doczekać do końca naszego życia. Czy jednak rzeczywiście musimy prosić mnichów o pomoc? Spróbujemy zaprojektować “szybki” algorytm, który pozwoli nam obliczyć pożądaną konfigurację. Żeby to jednak zrobić musimy dokładniej sprecyzować nasze zadanie. Przyjmijmy, że wieże są ponumerowane 0, 1 i 2. Na początku \(n\) pierścieni znajduje się na wieży o numerze 0. Kolejną wieżą w kierunku ruchu wskazówek zegara jest wieża o numerze 1, a następnie wieża o numerze 2. Przyjmijmy też, że pierścienie są ponumerowane od 1 do \(n\). Najmniejszym pierścieniem jest pierścień o numerze 1, pierścień o kolejnym rozmiarze ma numer 2, itd. aż do największego pierścienia, który będzie miał numer \(n\). Naszym celem będzie wyznaczenie dla każdego pierścienia numeru wieży, na której będzie się on znajdował po wykonaniu ruchu o numerze \(r\). Oto dokładna specyfikacja problemu:

Dane
Liczba całkowita \(r\), \(0 \le r \le 2^n - 1\).

Wynik
Tablica liczb całkowitych \(wieza[0..n+1]\) taka, że \(wieza[i]\) to numer wieży, na której znajduje się pierścień o numerze \(i\) po wykonaniu ruchu \(r\).

W celu zaprojektowania naszego algorytmu wygodnie będzie prześledzić jego wykonanie dla \(n = 5\). Dla każdego ruchu zapiszemy, który pierścień jest przemieszczany w tym ruch oraz w jakim kierunku: znak ‘+’ oznaczać będzie, że zgodnie z ruchem wskazówek zegara, natomiast znak ‘-’, że przeciwnie do ruchu wskazówek zegara.

r	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
pierścień	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1	5
kierunek	+	-	+	+	+	-	+	-	+	-	+	+	+	-	+	+

r	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
pierścień	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1
kierunek	+	-	+	+	+	-	+	-	+	-	+	+	+	-	+

Co możemy zaobserwować?

• Na początku, przed wykonaniem pierwszego ruchu, wszystkie pierścienie znajdują się na wieży o numerze 0.
• Pierścień o numerze \(i\) jest przemieszczany po raz pierwszy w ruchu o numerze \(2^{i-1}\), a następnie co \(2^i\) ruchów, czyli że pierścień o numerze 1 co 2 ruchy, pierścień o numerze 2 co 4 ruchy, pierścień o numerze 3 co 8 ruchów, itd.
• Pierścienie o numerach nieparzystych wędrują zgodnie z ruchem wskazówek zegara, natomiast pierścienie o numerach parzystych przeciwnie do ruchu skazówek zegara.

Wiedząc to wszystko, łatwo już obliczyć numer wieży, na której znajdzie się pierścień o numerze \(i\) po wykonaniu \(r\) ruchów. Jeśli \(r<2^{i-1}\), pierścień ani razu nie został ruszony, więc znajduje się on wciąż na wieży 0. W przeciwnym razie pierścień został ruszony

\(1 + (r-2^{i-1})/2^i\)

razy, gdzie "/" oznacza dzielenie bez reszty. Przy tym, jeśli to był pierścień o numerze nieparzystym, to wędrował po kolejnych wieżach 0, 1, 2, 0, 1, 2, ..., a zatem znajduje się on teraz na wieży o numerze \(k % 3\) (reszta z dzielenia). W przeciwnym razie znajduje się na wieży o numerze \(3- k % 3\), modulo 3.

Zauważmy, że w tym algorytmie dla każdego pierścienia wykonujemy stałą liczbę operacji arytmetycznych, zatem łączna liczba operacji arytmetycznych będzie “proporcjonalna” do liczby pierścieni, która jest dużo mniejsza niż możliwa liczba ruchów.

#include <iostream>
using namespace std;

void pozycja_hanoi(int n, unsigned long long r) {
    int wieza[n + 1]; // konfiguracja pierścieni po r ruchach

    unsigned long long potega_2 = 1;
    for (int i = 1; i <= n; ++i) {
        if (r < potega_2) // potega_2 == 2^(i-1)       
            wieza[i] = 0;
        else {
            unsigned long long k = 1 + (r - potega_2) / (2 * potega_2);
            if (i % 2 == 1)
                wieza[i] = k % 3;
            else
                wieza[i] = (3 - k % 3) % 3;
        }
        potega_2 *= 2;
    }

    // na koniec zadbajmy o ładne wypisywanie
    for (int w = 0; w < 3; ++w) {
        cout << w << ": ";
        for (int i = n; i >= 1; --i)
            if (wieza[i] == w)
                cout << i << " ";
        cout << endl;
    }
}

int main() {
    int n; // liczba pierścieni, n <= 63
    cin >> n;
    unsigned long long r; // liczba ruchów
    cin >> r;
    pozycja_hanoi(n, r);
}

0: 5 4 1 
1: 3 2 
2:

Powiedzmy, że mamy napisać program, który wczytuje liczbę naturalną \(n\) i wypisuje sumę liczb całkowitych od 1 do \(n\). Taki program pisaliśmy już w lekcji 6:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int suma = 0;
    for (int i = 1; i <= n; ++i)
        suma += i;
    cout << suma << endl;
}

Gdy uruchomimy nasz program kolejno dla \(n=100,1000,10\,000\), otrzymujemy następujące wyniki:

5050
500500
50005000

Gdy na wejściu podamy \(n=100\,000\), wynik programu może nas zaniepokoić:

705082704

Liczba wynikowa wyszła tu mniej "okrągła" niż poprzednio. Rzeczywiście, gdy uruchomimy nasz program dla \(n=200\,000\), otrzymamy wynik:

-1474736480

sugerujący, że w obliczeniach doszło do przekroczenia zakresu zmiennej \(suma\). Łatwo to poprawić, zmieniając typ zmiennej \(suma\).

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long suma = 0;
    for (int i = 1; i <= n; ++i)
        suma += i;
    cout << suma << endl;
}

Teraz dla \(n=100\,000\) mamy już dużo sensowniejszy wynik:

5000050000

A co się stanie, gdy temu programowi podamy na wejściu \(n=1\,000\,000\,000\)? Wówczas też otrzymamy sensowny wynik, ale program będzie już działał zauważalnie długo (u nas kilka sekund). To dlatego, że aby obliczyć wynik, program musi wykonać aż \(n\) dodawań. Zauważmy, że wykonanie miliarda dodawań zajmuje komputerowi zaledwie kilka sekund! Jeśli jednak rozwiązywalibyśmy takie zadanie w MAIN 2 i autor zadania ustawiłby limit czasu działania programu na sekundę, zapewne program działałby za długo, co objawiłoby się komunikatem: "Przekroczenie limitu czasu".

Okazuje się, że ten sam wynik można otrzymać dużo szybciej. Jeśli \(n\) jest parzyste, robimy to tak:

 1  +  2  + ... +  n/2
 n  + n-1 + ... + n/2+1
=======================
n+1 + n+1 + ... +  n+1 = (n+1)*n/2

Pewna znana anegdota głosi, że pewien nauczyciel matematyki w szkole podstawowej zlecił wszystkim uczniom klasy obliczenie sumy liczb od 1 do 100, aby mieć chwilę spokoju od lekcji. Tymczasem jeden z uczniów praktycznie natychmiast obliczył tę sumę, właśnie podanym wyżej sposobem, wprawiając nauczyciela w zdziwienie (i zapewne zakłopotanie). Według anegdoty uczniem tym był późniejszy wielki matematyk, Carl Friedrich Gauss.

Szczęśliwie otrzymany wzór działa także dla \(n\) nieparzystych, a do jego obliczenia wystarczy wykonać zaledwie kilka działań (zamiast miliarda działań jak poprzednio). Otrzymujemy następujący program, który kończy się błyskawicznie.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (long long)(n + 1) * n / 2 << endl;
}

Ponieważ wynik musimy przechowywać w typie long long, przy jego obliczaniu używamy rzutowania typu int na long long. Warto tu zauważyć dwie rzeczy: (1) nazwa typu long long składa się z dwóch słów, więc trzeba było umieścić ją w nawiasie przy rzutowaniu; (2) przy obliczaniu iloczynu wystarczyło tylko jeden czynnik zrzutować na typ long long, a już całe wyrażenie obliczyło się w typie long long.

A co by było, gdyby ograniczeniem górnym na \(n\) było, powiedzmy, \(10^{12}\) albo \(10^{18}\)? Wówczas wzór działałby równie szybko jak wcześniej, tylko nie mielibyśmy do dyspozycji żadnego typu danych w C++, w którym zmieściłby się wynik. A co jeśli jednak koniecznie musielibyśmy napisać taki program? Podpowiedź, jak sobie z tym poradzić, daje zadanie 3 z poprzedniej lekcji.

I jeszcze drugi przykład. Przypomnijmy program z funkcją sprawdzającą, czy dana liczba naturalna jest liczbą pierwszą. Od razu przedstawmy go w wersji wykonującej wszystkie obliczenia w typie long long.

#include <iostream>
using namespace std;

bool czy_pierwsza(long long n) {
    for (long long i = 2; i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

int main() {
    long long n;
    cin >> n;
    cout << czy_pierwsza(n) << endl;
}

Jak szybki jest ten program? Widzimy, że podobnie jak poprzednio wykonywanych tu z grubsza \(n\) operacji. Tym razem są to dzielenia. A zatem moglibyśmy się spodziewać, że dla \(n=1\,000\,000\,000\) program też będzie działać zauważalnie wolno. Tymczasem, gdy uruchomimy go dla takich danych, program działa natychmiastowo! Podobnie rzecz ma się, gdy \(n=10^{12}\) lub jest jeszcze większe. Jest tak dlatego, że gdy tylko program znajdzie jakiś dzielnik liczby \(n\), instrukcja return powoduje natychmiastowe przerwanie pętli for i program kończy się. Dla wszystkich wprowadzonych danych takim dzielnikiem było już \(i=2\).

Dużo inaczej sprawa wygląda, gdy np. takiego dzielnika w ogóle nie ma, czyli liczba \(n\) jest liczbą pierwszą. Wówczas dzielnie wykonamy wszystkie obroty pętli dla \(i=2,\ldots,n-1\). Gdy uruchomimy nasz program dla liczby \(n=1\,000\,000\,007\), która już jest liczbą pierwszą, na wynik będziemy musieli poczekać kilkanaście sekund. Lepiej nawet nie sprawdzać, ile czasu będzie to trwało dla liczb pierwszych rzędu \(10^{12}\) lub większych.

Czy możemy zatem jakoś usprawnić nasz program? Okazuje się, że tak. Ponadto, możemy do tego wykorzystać funkcję, którą dopiero co poznaliśmy!

Otóż jeśli liczba \(n\) nie jest liczbą pierwszą, to możemy ją przedstawić jako iloczyn dwóch liczb całkowitych różnych od 1. Czasem możemy to zrobić na kilka sposobów, np.:

36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6

Zauważmy jednak, że w każdym takim iloczynie mniejszy czynnik nie przekracza pierwiastka z \(n\). Jest to jasne: gdyby oba czynniki przekraczały \(\sqrt{n}\), to ich iloczyn byłby większy niż \(n\). Stąd wystarczy sprawdzić możliwe dzielniki \(i\) tylko do \(\sqrt{n}\), do obliczenia którego może posłużyć nam funkcja sqrt na liczbach rzeczywistych:

#include <iostream>
#include <cmath>
using namespace std;

bool czy_pierwsza(long long n) {
    int granica = int(sqrt(double(n)));
    for (int i = 2; i <= granica; ++i)
        if (n % i == 0)
            return false;
    return true;
}

int main() {
    long long n;
    cin >> n;
    cout << czy_pierwsza(n) << endl;
}

Zauważmy, że teraz do przechowywania zmiennej \(i\) wystarczył nam typ int. Ten program działa już zdecydowanie lepiej, gdyż zamiast \(n\) dzieleń wykonuje ich tylko \(\sqrt{n}\). Przykładowo, \(\sqrt{1\,000\,000\,007} \approx 31\,623\) i rzeczywiście program dla takich danych (a nawet większych danych) działa bardzo szybko.

Uwaga: Pętlę for w powyższym programie można także było zapisać bez używania funkcji sqrt. Jednak do tego celu potrzebna jest pętla for ze sprytniej zapisanym warunkiem:

    for (long long i = 2; i * i <= n; ++i)

Celem tej części technicznej było pokazanie, że efektywność naszych programów może mieć duże znaczenie. Temu, jak pisać szybkie i poprawne programy, poświęcony jest drugi z kursów w MAIN 2, czyli kurs podstaw algorytmiki.