Algoritmi de divizibilitate

Problemă cu sume parțiale

Se dă o matrice de dimensiuni N și M, de numere naturale, și un număr natural K; pentru fiecare celulă să se calculeze latura (impară) minimă a unui pătrat centrat pe celulă astfel încât suma pe acel pătrat să fie cel puțin K. Pătratul trebuie să fie inclus în matrice; dacă nu există niciunul trebuie să se afișeze -1.

Exemplu

Intrare:

4 6 10
1 2 3 4 5 6
36 25 16 9 4 1
7 7 7 7 7 7
10 8 10 3 3 3

Ieșire:

-1 -1 -1 -1 -1 -1
1 1 1 3 3 -1
-1 3 3 3 3 -1
1 -1 1 -1 -1 -1

Aflarea tuturor divizorilor

Funcția următoare calculează lista (neordonată) a divizorilor unui număr. Se folosește de faptul că divizorii sunt în perechi, cu excepția eventualului radical natural al numărului.

vector<int> divisors(int const x) {
    vector<int> div;
    int d;
    for (d = 1; d*d < x; ++d) {
        if (!(x % d)) {
            div.push_back(d);
            div.push_back(x / d);
        }
    }
    if (d*d == x) {
        div.push_back(d);
    }
    return div;
}

Aflarea tuturor factorilor primi

vector<int> prime_factors(int x) {
    vector<int> pf;
    int d = 2;
    while (d*d <= x && x != 1) {
        if (!(x % d)) {
            pf.push_back(d);
            do {
                x /= d;
            } while (!(x % d));
        }
        ++d;
    }
    if (x != 1) {
        pf.push_back(x);
    }
    return pf;
}

Cel mai mare divizor comun – Algoritmul lui Euclid

int gcd(int a, int b) {
    while (b != 0) {
        int const r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Exemplificare vizuală.

Ciurul lui Eratostene

Este un algoritm antic prin care se poate afla, pentru orice număr natural mai mic decât o limită, dacă e număr prim.

Se începe cu un vector de N elemente, inițial de valoare 0 (0 înseamnă număr prim și 1 înseamnă număr compus). Pozițiile 0 și 1 vor avea valoarea 1. Ideea algoritmului este: pentru fiecare element din vector începând cu 2, elementul este prim dacă s-a lucrat la elementele anterioare și încă este nemarcat, deoarece, dacă era compus, ar fi fost marcat anterior. Dacă este prim, se marchează toți multiplii elementului, în afară de el însuși.

Multiplii unui indice i sunt 2*i, 3*i etc. Deoarece multiplii până la i*i conțin un factor mai mic decât i, nu se mai procesează, fiind deja marcați prin acest factor mai mic.

vector<char> get_is_prime(int const size) {
    vector<char> sieve(size);
    sieve[0] = 1, sieve[1] = 1;
    for (int i = 2; i*i < size; ++i) {
        if (!sieve[i]) {
            for (int j = i*i; j < size; j += i) {
                sieve[j] = 1;
            }
        }
    }
    return sieve;
}

Algoritmi asemănători cu Ciurul lui Eratostene

Atenție de la ce multiplu începem să parcurgem vectorul. Dacă trebuie să numărăm toți factorii primi, parcurgem începând de la i, nu de la i*i. De asemenea, unii algoritmi cer să realizăm parcurgerea multiplilor tuturor numerelor, nu doar a celor prime, în cazul în care vrem să numărăm, de exemplu, toți divizorii.

Observații:

• Pentru orice număr sub 2310 sunt maxim 4 factori primi.
• Pentru orice număr sub 30030 sunt maxim 5 factori primi.
• Pentru orice număr sub 510510 sunt maxim 6 factori primi.
• Pentru orice număr sub 9699690 sunt maxim 7 factori primi.
• 15 factori primi sunt suficienți pentru orice număr natural de până la 2⁶⁴. Nu putem însă face vreun ciur de această dimensiune, deoarece nu există calculator cu atâta memorie.
• Numerele prime au un singur factor prim, adică numărul însuși.

Numărul de factori primi

De exemplu, 42 are factorii primi 2, 3 și 7.

vector<char> get_pf_count(int const size) {
    vector<char> sieve(size);
    sieve[0] = -1, sieve[1] = 0;
    for (int i = 2; i < size; ++i) {
        if (!sieve[i]) {
            for (int j = i; j < size; j += i) {
                ++sieve[j];
            }
        }
    }
    return sieve;
}

Deoarece pentru orice număr care încape în dimensiunea memoriei sunt mult sub 256 de factori primi, tipul char ar trebui să fie suficient pentru acest calcul.

Suma divizorilor

vector<int> get_divisor_sum(int const size) {
    vector<int> sieve(size);
    sieve[0] = -1;
    for (int i = 1; i < size; ++i) {
        for (int j = i; j < size; j += i) {
            sieve[j] += i;
        }
    }
    return sieve;
}

Cel mai mare/cel mai mic factor prim

vector<int> get_max_pf(int const size) {
    vector<int> sieve(size);
    sieve[0] = -1, sieve[1] = -1;
    for (int i = 2; i < size; ++i) {
        if (!sieve[i]) {
            for (int j = i; j < size; j += i) {
                sieve[j] = i;
            }
        }
    }
    return sieve;
}

vector<int> get_min_pf(int const size) {
    vector<int> sieve(size);
    sieve[0] = -1, sieve[1] = -1;
    for (int i = 2; i < size; ++i) {
        if (!sieve[i]) {
            sieve[i] = i;
            for (int j = i*i; j < size; j += i) {
                sieve[j] = i;
            }
        }
    }
    return sieve;
}

Algoritmi care folosesc Ciurul lui Eratostene

Lista numerelor prime

Pur și simplu generăm Ciurul lui Eratostene și apoi memorăm care indici din el au valoarea 0.

vector<int> all_prime_numbers(vector<int> const &is_prime) {
    vector<int> prime_numbers;
    for (int i = 0; i < is_prime.size(); ++i) {
        if (is_prime[i]) {
            prime_numbers.push_back(i);
        }
    }
    return prime_numbers;
}

Descompunerea în factori primi

Ne amintim că, pentru a descompune în factori primi un număr, căutam cu un toți factorii primi ai acestuia, folosind un for pentru a-i căuta. Problema este că, dintre numerele naturale, puține sunt numere prime, și nu are sens să le parcurgem pe toate când ne interesează doar numerele prime.

vector<int> prime_factors(vector<int> const &prime_numbers) {
    vector<int> pf;
    int i = 0;
    while (i < prime_numbers.size()
           && prime_numbers[i]*prime_numbers[i] <= x
           && x != 1) {
        int const d = prime_numbers[i];
        if (!(x % d)) {
            pf.push_back(d);
            do {
                x /= d;
            } while (!(x % d));
        }
        ++i;
    }
    if (x != 1) {
        pf.push_back(x);
    }
    return pf;
}

Acest algoritm poate descompune numere până la pătratul limitei ciurului.

Descompunerea rapidă în factori primi a numerelor mai mici

Să considerăm că ciurul are dimensiunea de 16 777 216, sau 2²⁴, o dimensiune rezonabilă (ocupă 16 megaocteți, în contextul în care acum în majoritatea problemelor de concurs se oferă 32–256 MB).

Pentru această dimensiune putem descompune în factori primi orice număr de până la pătratul ei, adică 2⁴⁸, adică 281 474 976 710 656, adică orice număr natural cu până la 14 cifre zecimale.

Dacă nu avem nevoie de descompunerea numerelor atât de mari, putem lucra cu un algoritm mai eficient. Acesta este un algoritm în care numărul de operații e proporțional cu suma exponenților factorilor primi. Dacă algoritmul anterior are ca număr maxim de pași numărul de numere prime disponibile, acesta are ca număr maxim de pași suma exponenților. Pentru numere de până la 2²⁴, suma exponenților e maxim 23 (se obține chiar folosind doar factori de 2, care cresc cel mai lent).

vector<int> prime_factors(vector<int> const &min_pf) {
    vector<int> pf;
    int last_factor = -1;
    while (x != 1) {
        if (last_factor != min_pf[x]) {
            pf.push_back(min_pf[x]);
            last_factor = min_pf[x];
        }
        x /= min_pf[x];
    }
    return pf;
}

Acest algoritm se folosește de tehnica precedentă pentru a genera factorul prim minim. Dacă numărul nu este 1, luăm acest factor prim și sărim la numărul fără factorul prim.