Prosti brojevi i faktorizacija

Prirodan broj veći od 1 je prost ako je deljiv samo sa 1 i sa samim sobom. Broj 1 nije prost. Na ovoj strani obrađujemo tri srodna problema koja se često javljaju kao deo složenijih takmičarskih zadataka:

• provera da li je broj prost i ispis svih prostih brojeva na intervalu,
• određivanje svih delilaca broja,
• faktorizacija, odnosno rastavljanje broja na proste činioce.

Prvo rešenje: traženje prvog delioca

Posle učitavanja brojeva a i b prolazimo kroz sve brojeve sa intervala i za svaki proveravamo da li je prost. Funkcija za proveru počinje od delioca 2 i povećava ga sve dok ne naiđe na broj sa kojim je ispitivani broj deljiv. Ako je taj prvi delilac manji od samog broja, broj nije prost; ako je jednak broju, broj je prost.

#include <iostream>
using namespace std;

// Prva (najsporija) verzija: traži prvi delilac broja b počev od 2
bool isProst(long long b)
{
    if (b < 2)          // 0 i 1 nisu prosti brojevi
        return false;

    long long d = 2;
    // Povećavamo d sve dok ne naiđemo na broj sa kojim je b deljiv.
    // Petlja se sigurno završava, jer je b deljiv bar samim sobom.
    while (b % d != 0)
    {
        d++;
    }

    // Ako je prvi pronađeni delilac manji od b, broj nije prost
    return d == b;
}

int main()
{
    long long a, b, c = 0;   // c - broj ispisanih prostih brojeva
    cin >> a >> b;

    for (long long i = a; i <= b; i++)
    {
        if (isProst(i))
        {
            cout << i << " ";
            c++;
            if (c % 10 == 0)     // posle svakih 10 brojeva novi red
                cout << endl;
        }
    }

    return 0;
}

Za prost broj n petlja se izvršava skoro n puta, pa je ovaj algoritam prespor već za brojeve reda 10^9. Ranije se završava samo kada broj ima mali delilac.

Svođenje broja provera sa n na √n

Ako je d delilac broja n, onda je i n/d njegov delilac. Na primer, 6 je delilac broja 42, ali to je i 42/6 = 7. Bar jedan od ta dva delioca mora biti manji ili jednak √n: kada bi oba bila veća, njihov proizvod bi bio veći od n. Ako su jednaki, n je potpun kvadrat i oba su jednaka √n.

Zaključak: ako broj nema delilac između 2 i √n, onda je prost. Dovoljno je najviše √n provera.

#include <iostream>
using namespace std;

// Proverava delioce samo do korena iz n
bool isProst(long long n)
{
    if (n < 2)
        return false;

    long long d = 2;
    while (d * d <= n)       // ekvivalentno sa d <= √n, bez rada sa realnim brojevima
    {
        if (n % d == 0)      // pronađen delilac: n nije prost
            return false;
        d = d + 1;
    }
    return true;             // nema delioca do √n: n je prost
}

int main()
{
    long long a, b, c = 0;
    cin >> a >> b;

    for (long long i = a; i <= b; i++)
    {
        if (isProst(i))
        {
            cout << i << " ";
            c++;
            if (c % 10 == 0)
                cout << endl;
        }
    }

    return 0;
}

Funkcija najpre odbacuje brojeve manje od 2. Zatim ispituje delioce od 2 do √n, uključujući i √n. Uslov se piše kao d * d <= n, da bismo izbegli računanje korena i greške zaokruživanja. Čim se pronađe delilac, funkcija vraća false.

Ubrzanje pomoću oblika 6k ± 1

Svaki prost broj veći od 3 ima oblik 6k − 1 ili 6k + 1. Ostali oblici (6k, 6k ± 2, 6k + 3) deljivi su sa 2 ili sa 3. Zato je dovoljno da posebno proverimo deljivost sa 2 i 3, a zatim kao delioce ispitujemo samo brojeve 5, 7, 11, 13, 17, 19, ... To je oko tri puta manje provera.

#include <iostream>
using namespace std;

// Provera samo delilaca oblika 6k - 1 i 6k + 1
bool isProst(long long n)
{
    if (n < 2)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)   // parni brojevi i umnošci broja 3
        return false;

    // Preostali mogući delioci su 5, 7, 11, 13, 17, 19, ...
    // odnosno brojevi oblika 6k - 1 i 6k + 1, k = 1, 2, 3, ...
    for (long long d = 5; d * d <= n; d += 6)
    {
        if (n % d == 0 || n % (d + 2) == 0)   // d = 6k - 1, d + 2 = 6k + 1
            return false;
    }
    return true;
}

int main()
{
    long long a, b, c = 0;
    cin >> a >> b;

    for (long long i = a; i <= b; i++)
    {
        if (isProst(i))
        {
            cout << i << " ";
            c++;
            if (c % 10 == 0)
                cout << endl;
        }
    }

    return 0;
}

Određivanje svih delilaca broja

Određivanje delilaca treba razlikovati od faktorizacije. Delioci broja 12 su 1, 2, 3, 4, 6, 12, svaki naveden po jednom. Faktorizacija je zapis broja kao proizvoda prostih činilaca: 12 = 2 · 2 · 3.

I ovde je dovoljno ispitati brojeve do √n, jer svaki delilac d ima svoj par n/d. Delioci broja 12 su parovi (1, 12), (2, 6), (3, 4), a delioci broja 16 su (1, 16), (2, 8), (4, 4). Kod broja 16 vidimo da je 4 u paru sa samim sobom, jer je 4 = √16.

#include <iostream>
using namespace std;

const int DIM = 10000;
long long d[DIM];   // d[1], d[2], ..., d[m] - pronađeni delioci

// Pronalazi sve delioce broja n; vraća njihov broj m
long long sviDelioci(long long n)
{
    long long m = 0;
    long long i = 1;

    // Delioci dolaze u parovima (i, n / i), pa je dovoljno
    // ispitati brojeve i za koje je i * i < n.
    while (i * i < n)
    {
        if (n % i == 0)
        {
            d[m + 1] = i;        // manji delilac iz para
            d[m + 2] = n / i;    // veći delilac iz para
            m = m + 2;
        }
        i = i + 1;
    }

    // Ako je n potpun kvadrat, koren se dodaje samo jednom
    if (i * i == n)
    {
        m = m + 1;
        d[m] = i;
    }

    return m;
}

int main()
{
    long long N, m;
    cin >> N;

    m = sviDelioci(N);

    for (int i = 1; i <= m; i++)
    {
        cout << d[i] << endl;
    }

    return 0;
}

Delioci se ispisuju u parovima (za 12: 1, 12, 2, 6, 3, 4). Ako su potrebni u rastućem redosledu, niz treba sortirati. Pošto se ispituje samo do √n, program radi brzo i za brojeve reda 10^12.

Faktorizacija broja N

Faktorizacija broja je njegovo rastavljanje na proste činioce, odnosno zapis u obliku:

n = p1^a1 · p2^a2 · ... · pk^ak

Kod određivanja delilaca, posle pronađenog delioca prelazi se odmah na sledeći. Kod faktorizacije se deljenje istim deliocem ponavlja dokle god je broj deljiv njime. Zato su svi pronađeni delioci automatski prosti: kada stignemo do, na primer, delioca 4, sve dvojke su već izdeljene, pa broj više nije deljiv sa 4.

#include <iostream>
using namespace std;

const int DIM = 100;

int a[DIM];   // a[k] - izložilac k-tog prostog činioca
int p[DIM];   // p[k] - k-ti prost činilac

// Rastavlja n na proste činioce; vraća broj različitih činilaca k
int faktorizacija(int n)
{
    int k = 0;
    int d = 2;

    // Uslov d <= n / d je isto što i d * d <= n,
    // ali ne može da izazove prekoračenje opsega tipa int.
    while (d <= n / d)
    {
        if (n % d == 0)
        {
            k = k + 1;
            p[k] = d;
            a[k] = 0;   // izložilac koji se pamti u nizu a

            while (n % d == 0)   // delimo sa d dok god je moguće
            {
                n = n / d;
                a[k] = a[k] + 1;
            }
        }
        d = d + 1;
    }

    // Ako je posle deljenja ostalo n > 1, to je prost činilac
    // veći od korena iz početnog broja (javlja se samo jednom).
    if (n > 1)
    {
        k = k + 1;
        p[k] = n;
        a[k] = 1;
    }

    return k;
}

int main()
{
    int N, k;
    cin >> N;

    k = faktorizacija(N);

    // Ispis svakog prostog činioca onoliko puta koliko se pojavljuje
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= a[i]; j++)
        {
            cout << p[i] << endl;
        }
    }

    return 0;
}

• Niz p čuva proste činioce, a niz a njihove izložioce.
• Ako posle petlje ostane n > 1, to je prost činilac veći od korena početnog broja. Na primer, za N = 26 petlja izdeli dvojku, a ostatak 13 je poslednji činilac.
• Za N = 360 program ispisuje 2, 2, 2, 3, 3, 5, jer je 360 = 2^3 · 3^2 · 5.

Zadatak: Kvadratni parovi — primena faktorizacije

Dat je niz a dužine n. Potrebno je odrediti broj parova indeksa (i, j), gde je 1 ≤ i < j ≤ n, za koje važi da je proizvod ai · aj jednak kvadratu nekog prirodnog broja.

Drugim rečima, tražimo koliko parova elemenata iz niza daje proizvod koji je savršeni kvadrat.

x = p1^e1 * p2^e2 * ... * pk^ek

72 = 2^3 * 3^2  -> jezgro je 2
18 = 2^1 * 3^2  -> jezgro je 2
16 = 2^4        -> jezgro je 1

a_i * a_j je kvadrat  ⇔  jezgra brojeva a_i i a_j su ista

 72 = 2^3 * 3^2 

 3^2 

 2^3 = 2^2 * 2 

 2^3 = (2^2) * 2 

 72 = 2^3 * 3^2 -> jezgro je 2 
18 = 2^1 * 3^2 -> jezgro je 2 

 72 * 18 =
 2^(3+1) * 3^(2+2) =
 2^4 * 3^4 

 c brojeva koji mogu međusobno da formiraju kvadratni proizvod 

 c * (c - 1) / 2 

 a, b, c, d 

 (a,b) (a,c) (a,d) (b,c) (b,d) (c,d) 

 4 * 3 / 2 = 6 

Vremenska složenost: O(M log log M + n log M) ili približno O(M + n log M)
Memorijska složenost: O(M)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

/*
    Pravimo niz najmanjih prostih delilaca (spf).
    spf[x] = najmanji prost broj koji deli x.
*/
vector<int> napravi_spf(int maxV) {
    vector<int> spf(maxV + 1, 0);

    for (int i = 2; i <= maxV; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            if ((ll)i * i <= maxV) {
                for (ll j = 1LL * i * i; j <= maxV; j += i) {
                    if (spf[j] == 0) spf[j] = i;
                }
            }
        }
    }

    return spf;
}

/*
    Funkcija koja vraća squarefree jezgro broja x.

    Tokom faktorizacije pratimo parnost eksponenata:
    - ako se prost faktor pojavljuje neparan broj puta, on ostaje u jezgru
    - ako se pojavljuje paran broj puta, on se "poništava"
*/
int jezgro(int x, const vector<int> &spf) {
    int rezultat = 1;

    while (x > 1) {
        int p = spf[x];
        int cnt = 0;

        while (x % p == 0) {
            x /= p;
            cnt++;
        }

        // Ako je eksponent neparan, zadržavamo p u jezgru
        if (cnt % 2 == 1) {
            rezultat *= p;
        }
    }

    return rezultat;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    int maxV = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        maxV = max(maxV, a[i]);
    }

    // Pravimo SPF niz samo do najvećeg broja iz ulaza
    vector<int> spf = napravi_spf(maxV);

    /*
        cnt[jezgro] = koliko puta se određeno jezgro pojavilo
        Ako su dva broja istog jezgra, njihov proizvod je savršen kvadrat.
    */
    unordered_map<int, long long> cnt;

    for (int x : a) {
        int k = jezgro(x, spf);
        cnt[k]++;
    }

    ll odgovor = 0;

    for (auto &par : cnt) {
        ll c = par.second;
        odgovor += c * (c - 1) / 2;
    }

    cout << odgovor << '\n';

    return 0;
}