Numere prime și divizori la BAC: algoritmi C++

La BAC informatică, un număr prim se verifică prin căutarea unui divizor propriu. Un număr natural mai mare decât unu este prim dacă are exact doi divizori pozitivi: unu și el însuși. Nu trebuie să testezi toate valorile până la număr; este suficient să verifici posibilii divizori până la rădăcina sa pătrată, inclusiv.

Lecția urmărește implementarea algoritmului, justificarea limitei și cazurile care produc frecvent erori: zero, unu, doi și pătratele perfecte. Nu este o listă de numere prime de memorat. Exemplele folosesc numere naturale de cel mult un miliard, pentru care testarea prin divizori este potrivită unui exercițiu elementar.

Perechile de divizori explică limita

Dacă d divide numărul pozitiv n, atunci există numărul întreg q=n/d, iar produsul lor este n. Divizorii pot fi grupați în perechi. Pentru treizeci și șase, perechile sunt unu cu treizeci și șase, doi cu optsprezece, trei cu doisprezece, patru cu nouă și șase cu șase.

În fiecare pereche, cel puțin un număr este mai mic sau egal cu rădăcina pătrată a lui n. Dacă ambele ar fi strict mai mari, produsul lor ar depăși n. De aceea, dacă nu găsești niciun divizor între doi și acea limită, nu poate exista nici un divizor propriu mai mare care să fie primul descoperit.

Schema de decizie: n<2 → nu este prim; altfel cauți un divizor d≥2 cu d*d≤n; găsit → compus; niciunul găsit → prim.

n	Divizor decisiv	Concluzie
1	Nu aplicăm căutarea	Nu este prim
2	Nu există candidat până la limită	Prim
21	3	Compus
29	Niciunul dintre 2, 3, 4, 5	Prim
49	7	Compus

Implementare sigură în C++

#include <iostream>
using namespace std;

bool prim(unsigned long long n) {
    if (n < 2) return false;
    for (unsigned long long d = 2; d <= n / d; ++d) {
        if (n % d == 0) return false;
    }
    return true;
}

int main() {
    unsigned long long n;
    cin >> n;
    cout << (prim(n) ? "DA" : "NU");
    return 0;
}

Condiția d<=n/d exprimă limita fără să calculeze produsul d*d, care ar putea depăși un tip numeric pentru domenii mai mari. Împărțirea este sigură deoarece d începe de la doi și crește, deci nu devine zero. Pentru numerele naturale pozitive, comparația cu câtul întreg păstrează exact condiția necesară.

Instrucțiunea care returnează fals poate apărea imediat ce găsești un divizor. În schimb, returnarea valorii adevărat trebuie făcută după terminarea tuturor testelor. Un singur candidat care nu divide numărul nu dovedește că numărul este prim: douăzeci și unu nu este divizibil cu doi, dar este divizibil cu trei.

De ce limita trebuie inclusă

Pentru n=49, rădăcina pătrată este șapte. Dacă folosești o condiție strictă, testezi numai valorile mai mici decât șapte și nu descoperi divizorul decisiv. Algoritmul poate declara greșit că numărul este prim.

Același defect apare pentru patru, nouă, douăzeci și cinci și alte pătrate ale unor numere prime. Acestea sunt teste foarte utile: au un divizor propriu exact la limită. Un set de verificare care conține numai numere pare și numere prime poate rata problema.

Nu confunda includerea limitei cu testarea numărului însuși. Pentru un număr mai mare decât unu, rădăcina sa pătrată este mai mică decât numărul. Bucla nu respinge astfel orice intrare pentru că ar fi divizibilă cu ea însăși.

Optimizarea după tratarea numărului doi

Poți trata separat numărul doi, apoi respinge toate celelalte numere pare. Pentru valorile impare rămase, testezi numai divizori impari, pornind de la trei și crescând cu doi. Nu ai nevoie să verifici patru, șase sau opt: dacă unul dintre acestea ar divide un număr, doi l-ar divide deja.

Ordinea condițiilor contează. Dacă respingi mai întâi toate numerele pare, îl respingi și pe doi, deși este prim. O ordine corectă este: valori sub doi, egalitate cu doi, paritate, apoi candidații impari. Poți păstra și varianta simplă care testează toți candidații; ea este mai ușor de urmărit și rămâne corectă.

Optimizarea reduce aproximativ la jumătate numărul candidaților testați, dar ordinul de timp rămâne același: proporțional cu rădăcina pătrată a lui n în cazul nefavorabil. Memoria suplimentară este constantă. Dacă trebuie verificate foarte multe numere dintr-un interval, o sită poate fi mai potrivită, însă aceasta este o altă strategie.

Numărarea divizorilor fără dublarea rădăcinii

Perechile sunt utile și pentru numărul divizorilor unui număr pozitiv. Pentru fiecare d de la unu până la limită, verifici dacă divide n. Dacă da, ai de obicei doi divizori: d și n/d. Excepția apare când cele două valori sunt egale; atunci numeri un singur divizor.

Pentru treizeci și șase, primele patru perechi distincte contribuie cu opt divizori, iar perechea șase cu șase contribuie cu unul singur. În total sunt nouă divizori pozitivi. Dacă adaugi mereu doi, obții zece și numeri șase de două ori.

Pentru un număr pozitiv care nu este pătrat perfect, toate perechile au elemente distincte, deci numărul divizorilor este par. Pentru un pătrat perfect, rădăcina rămâne singură, deci numărul divizorilor este impar. Această observație explică rezultatul; nu trebuie memorată ca o regulă fără legătură cu algoritmul.

Zero trebuie exclus din problema numărării divizorilor pozitivi: orice număr întreg pozitiv îl divide. Nu există un număr finit de divizori pozitivi ai lui zero. Funcția de primalitate îl poate respinge imediat, dar un algoritm pentru numărul divizorilor necesită domeniul n≥1.

Atelier de depanare

Un elev scrie: „pentru fiecare candidat, dacă restul este zero, numărul nu este prim; altfel, numărul este prim”. Eroarea este concluzia din ramura „altfel”. Ea este formulată înainte să fie încercați ceilalți candidați. Pentru cincisprezece, testul cu doi ar anunța primalitatea, deși trei este divizor.

Corectarea constă în păstrarea unei concluzii provizorii până la final sau în returnarea imediată numai când apare dovada că numărul este compus. Primalitatea se confirmă după epuizarea candidaților necesari. Nu rezolvi eroarea adăugând încă un exemplu particular, ci reparând locul concluziei în algoritm.

Exerciții cu soluții explicate

1. Ce rezultat trebuie să producă funcția pentru zero, unu, doi și patru? Răspuns: nu, nu, da, nu. Aceste valori verifică respingerea domeniului neprim, cazul celui mai mic prim și includerea rădăcinii în căutare.

2. De ce este suficient să testezi candidații până la zece pentru n=101? Răspuns: unsprezece la pătrat depășește o sută unu. Orice divizor propriu mai mare ar avea un partener mai mic, care ar fi fost deja testat. Niciun candidat până la zece nu divide numărul, deci este prim.

3. Câți divizori pozitivi are n=16? Răspuns: cinci: unu, doi, patru, opt și șaisprezece. Perechile sunt unu cu șaisprezece, doi cu opt și patru cu patru, ultima numărând o singură valoare.

4. Găsește un exemplu care demontează condiția strictă d*d<n. Răspuns: nouă. Candidatul trei trebuie testat, dar produsul său cu el însuși este egal cu nouă, nu strict mai mic.

Întrebări frecvente

Unu este prim?

Nu. Are un singur divizor pozitiv, iar definiția cere exact doi. Trebuie respins înaintea buclei, altfel lipsa candidaților îl poate face să pară prim.

Pot testa până la jumătatea numărului?

Da, pentru corectitudine este suficient, dar faci inutil mai mulți pași. Limita rădăcinii rezultă din perechile de divizori și este mult mai eficientă.

Trebuie să folosesc o funcție pentru radical?

Nu. Condiția d<=n/d evită calculul unui radical în virgulă mobilă și problemele de rotunjire la limită. Este suficientă aritmetica întreagă.

Aplică verificările pe variante BAC cu bareme, apoi explică fiecare caz-limită prin definiție, în spiritul învățării prin înțelegere. Poți cere feedback pe codul tău unui profesor de informatică. Reper curricular: programa oficială de informatică, algoritmi elementari și divizibilitate, pentru specializarea aleasă.