Divizibilitate și numere prime în C++

Un număr întreg nenul d este divizor al lui n dacă împărțirea lui n la d este exactă. În C++, pentru numere întregi și d != 0, verificarea se scrie n % d == 0. În această lecție căutăm divizori pozitivi și lucrăm cu numere naturale.

Ai nevoie de operatorul rest și de structuri repetitive. Vei învăța să cauți divizori în perechi și să verifici dacă un număr este prim.

Divizorii vin în perechi

Pentru n = 36, perechile de divizori sunt (1, 36), (2, 18), (3, 12), (4, 9) și (6, 6). Dacă ai găsit un divizor d, ai găsit și divizorul n / d.

Nu trebuie să continui căutarea dincolo de rădăcina pătrată: în fiecare pereche există un membru cel mult egal cu ea. La un pătrat perfect, perechea din mijloc conține de două ori aceeași valoare, deci o numărăm o singură dată.

La un pătrat perfect, perechea din mijloc adaugă un singur divizor.

Numărul divizorilor pozitivi

Citim n, cu 1 <= n <= 1000000000, și afișăm câți divizori pozitivi are.

#include <iostream>

int main() {
    long long n = 0;
    std::cin >> n;
    int numarDivizori = 0;
    for (long long d = 1; d <= n / d; ++d) {
        if (n % d == 0) {
            ++numarDivizori;
            if (d != n / d) {
                ++numarDivizori;
            }
        }
    }
    std::cout << numarDivizori << '\n';
    return 0;
}

Pentru 36, rezultatul este 9: divizorii sunt 1, 2, 3, 4, 6, 9, 12, 18, 36. Pentru 1, există un singur divizor pozitiv, chiar 1.

Condiția d <= n / d exprimă limita rădăcinii pătrate pentru valori pozitive. Ea evită calculul lui d * d, care ar putea depăși tipul pentru limite mai mari. d începe de la 1, deci împărțirea din condiție nu are numitor zero.

Numărul zero nu este inclus în această problemă: orice întreg pozitiv divide zero, deci nu am obține o listă finită de divizori pozitivi.

Ce este un număr prim

Un număr natural mai mare decât 1 este prim dacă are exact doi divizori pozitivi: 1 și el însuși. 2 este prim; 1 și 0 nu sunt prime. Pentru a demonstra că un număr mai mare decât 1 nu este prim, este suficient să găsești un singur divizor între 2 și rădăcina sa pătrată.

#include <iostream>

int main() {
    long long n = 0;
    std::cin >> n;
    bool prim = n >= 2;
    for (long long d = 2; prim && d <= n / d; ++d) {
        if (n % d == 0) {
            prim = false;
        }
    }
    if (prim) {
        std::cout << "PRIM" << '\n';
    } else {
        std::cout << "NEPRIM" << '\n';
    }
    return 0;
}

Aici intrarea poate fi între 0 și 1000000000. Pentru 2, bucla nu are niciun candidat de verificat, iar rezultatul este PRIM. Pentru 49, divizorul 7 face ca variabila prim să devină falsă. Condiția buclei împiedică apoi alte încercări inutile.

Greșeli și cost

Limita trebuie să includă egalitatea. Dacă verifici numai divizori strict mai mici decât rădăcina pătrată, poți clasifica greșit 49. Nu număra de două ori rădăcina unui pătrat perfect și nu considera 1 prim.

În cel mai nefavorabil caz, numărul încercărilor crește ca rădăcina pătrată a lui n: timp O(sqrt(n)), memorie suplimentară O(1). Aceasta este o metodă potrivită pentru un număr și limitele date. Pentru multe întrebări de primalitate într-un interval, vei studia ulterior ciurul lui Eratostene.

Exersează

1. Câți divizori pozitivi are 12?
2. Care dintre 1, 2, 9, 13, 25 sunt prime?
3. De ce d = 1 nu poate demonstra că un număr este compus?
4. Ce caz verifică testul n = 49?

Răspunsuri: șase, anume 1, 2, 3, 4, 6, 12; sunt prime 2 și 13; unu divide orice număr întreg; testul verifică includerea rădăcinii pătrate în căutare.

Continuă cu generarea șirurilor, unde fiecare termen este construit după o regulă.

Întrebări frecvente

Cum verific dacă a este divizibil cu b?

Pentru b nenul, testezi a%b==0. Divizorul zero este interzis și trebuie exclus înainte de efectuarea operației.

De ce verific divizori numai până la rădăcină?

Divizorii apar în perechi al căror produs este numărul. Dacă există un divizor netrivial, cel puțin unul din pereche nu depășește rădăcina.

Este unu număr prim?

Nu. Un număr prim are exact doi divizori pozitivi distincți. Unu are un singur divizor pozitiv și este tratat separat.

Cum evit overflow în condiția d*d<=n?

Pentru numere pozitive poți folosi d<=n/d. Această formulă evită produsul intermediar, cu condiția ca d să fie nenul.

Care este diferența dintre testul de primalitate și ciur?

Testul verifică de regulă un număr, iar ciurul precalculează răspunsuri pentru un interval întreg. Alegerea depinde de limite și de numărul întrebărilor.