Divizibilitate și divizori

Testul de divizibilitate, cum găsești toți divizorii în √n pași și de ce jumătate din problemele de la examen se reduc la asta.

Testul

a se divide cu b dacă restul împărțirii este zero:

if (a % b == 0)
    cout << b << " divide pe " << a;

Toată divizibilitatea din programare pornește de aici.

Toți divizorii, varianta naivă

for (int d = 1; d <= n; d++)
    if (n % d == 0)
        cout << d << " ";

E corect, dar face n pași. Pentru n = 10⁹ este prea lent.

Toți divizorii, varianta bună

Divizorii vin în perechi. Dacă d divide pe n, atunci și n / d divide pe n. Dintre cei doi, unul este mereu ≤ √n.

Pentru n = 36, perechile sunt (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Ne oprim la 6, adică la √36.

for (int d = 1; d * d <= n; d++)
    if (n % d == 0) {
        cout << d << " ";
        if (d != n / d)
            cout << n / d << " ";
    }

Testul d != n / d te împiedică să afișezi de două ori rădăcina atunci când n este pătrat perfect. Fără el, la 36 l-ai afișa pe 6 de două ori.

Ai coborât de la n pași la √n. Pentru un miliard, asta înseamnă vreo treizeci de mii de pași în loc de un miliard. Este cea mai profitabilă optimizare din tot programul de bac și o vei folosi peste tot.

Despre scriere: e mai bine d * d <= n decât d <= sqrt(n). Prima variantă lucrează numai cu întregi. A doua calculează la fiecare pas un radical în virgulă mobilă și, din cauza aproximării, poate greși exact la limită.

Dacă n poate ajunge pe la 10⁹, d * d mai încape într-un int. Pentru valori mai mari, folosește long long.

Numărul de divizori și suma lor

Folosești aceeași buclă, doar că acumulezi altceva:

int cati = 0;
long long suma = 0;
for (int d = 1; d * d <= n; d++)
    if (n % d == 0) {
        cati++;
        suma += d;
        if (d != n / d) {
            cati++;
            suma += n / d;
        }
    }

Divizori proprii

La bacalaureat, divizorii proprii ai lui n sunt divizorii diferiți de 1 și de n. Enunțul o spune de obicei explicit, dar citește definiția de fiecare dată. Un număr perfect este egal cu suma divizorilor săi mai mici decât el, deci cu 1 inclus: 6 = 1 + 2 + 3, iar 28 = 1 + 2 + 4 + 7 + 14.

long long suma = 0;
for (int d = 1; d * d <= n; d++)
    if (n % d == 0) {
        suma += d;
        if (d != n / d) suma += n / d;
    }
suma -= n;              // scot numărul însuși

if (suma == n) cout << "perfect";

E mai simplu să aduni tot și să scazi n la final decât să tratezi cazul în buclă.

Atenție la n = 1: singurul divizor este 1, iar suma divizorilor mai mici decât el este 0. Codul de mai sus dă 1 - 1 = 0, deci funcționează corect.

Criterii de divizibilitate

Îți folosesc mai ales la Subiectul I, unde trebuie să răspunzi fără să calculezi:

În program nu ai nevoie de ele, pentru că n % 3 == 0 e mai simplu decât să calculezi suma cifrelor. Le folosești când lucrezi pe hârtie.

Un exemplu complet

Se citește un număr natural n, mai mare decât 1. Să se afișeze cel mai mare divizor al lui n mai mic decât n.

Prima idee ar fi să cauți de la n-1 în jos. Pentru un număr prim, asta înseamnă n pași.

Există o cale mai bună. Cel mai mare divizor al lui n mai mic decât n este n / p, unde p este cel mai mic divizor mai mare decât 1.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int p = 2;
    while (p * p <= n && n % p != 0)
        p++;

    if (p * p > n)
        cout << 1;      // n e prim: singurul divizor mai mic decât n e 1
    else
        cout << n / p;

    return 0;
}

Ideea de a căuta divizorul mic ca să afli divizorul mare apare des. Reține-o ca tipar, nu ca formulă.

De reținut

• n % d == 0 este tot testul de divizibilitate.
• Divizorii vin în perechi în jurul lui √n, așa că e destul să cauți până acolo.
• Scrie d * d <= n, nu d <= sqrt(n).
• Nu număra de două ori rădăcina când n e pătrat perfect.
• Cel mai mare divizor mai mic decât n se află din cel mai mic divizor prim.