Cum verific dacă un număr este prim în C++?

Tratezi n < 2 separat, apoi cauți un divizor de la 2 până la radical din n, cu condiția d * d <= n. Dacă nu găsești niciunul, n este prim.

Un număr este prim dacă are exact doi divizori, 1 și el însuși. Testul corect și rapid arată așa:

bool esteprim(int n) {
    if (n < 2) return false;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return false;
    return true;
}

Trei lucruri fac diferența între „merge” și „ia toate punctele”:

• n < 2 se tratează separat. 0 și 1 nu sunt prime. Fără această linie, bucla nu pornește și funcția le declară prime.
• Se caută doar până la radical din n. Orice număr compus are un divizor cel mult egal cu radicalul său: dacă n = a · b cu a ≤ b, atunci a ≤ √n. Pentru n de un miliard, faci vreo treizeci de mii de pași în loc de un miliard. La bac se punctează eficiența, deci d <= n / 2 sau d < n pierd puncte.
• Condiția are ≤, nu <. Se scrie d * d <= n. Cu <, pătratele numerelor prime (4, 9, 25, 49) ar fi declarate prime.

Scrii d * d <= n și nu d <= sqrt(n) ca să rămâi la întregi. Lecția despre numere prime demonstrează de ce ajunge radicalul.

Lecția care merge mai departe: Numere prime