Divizibilitate, numere prime și c.m.m.d.c.

Bucla care vizitează toți divizorii lui n, de la 1 la el însuși:

pentru d ← 1, n execută
    dacă n mod d = 0 atunci
        scrie d
    ■
■

for (int d = 1; d <= n; d++) {
    if (n % d == 0) {
        // d este divizor
    }
}

Dacă d divide n, atunci și n / d divide n: divizorii lui 12 sunt perechile (1, 12), (2, 6), (3, 4). Consecință utilă: orice divizor mai mare ca radicalul are perechea sub radical, deci multe căutări se pot opri la d * d <= n. Pătratele perfecte au un divizor singuratic (6 pentru 36), de aceea au număr impar de divizori.

Fanion care rămâne 1 doar dacă nu există divizor propriu până la radical:

ok ← 1
dacă n < 2 atunci
    ok ← 0
■
d ← 2
cât timp d * d ≤ n execută
    dacă n mod d = 0 atunci
        ok ← 0
    ■
    d ← d + 1
■

int ok = 1;
if (n < 2) {
    ok = 0;
}
for (int d = 2; d * d <= n; d++) {
    if (n % d == 0) {
        ok = 0;
    }
}

Cu condiția strictă d * d < n, bucla nu testează niciodată d = radical(n): 25 ar ieși prim, pentru că d = 5 nu e încercat (5·5 = 25 nu e < 25). Scrie mereu d * d <= n. La fel de important: n < 2 trebuie tratat separat, altfel 0 și 1 trec ca prime.

Prin împărțiri (rapid) și prin scăderi repetate (clasic):

cât timp b ≠ 0 execută
    r ← a mod b
    a ← b
    b ← r
■

while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
}
// răspunsul este a

După bucla lui Euclid, b este 0 și a este c.m.m.d.c.: valorile inițiale s-au pierdut. Dacă mai ai nevoie de ele (de exemplu la cmmmc = a * b / cmmdc), salvează copii înainte de buclă:

int x = a;
int y = b;
while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
}
// x = cmmdc; a și b sunt neatinse