Divizibilitate

#include <iostream>
#include <fstream>
using namespace std;

/* Numarul divizorilor lui n: divizorii se cauta
   pana la radacina patrata, cu perechea lor n/d. */
int nrDiv(int n) {
    int nr = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            nr++;              // divizorul d
            if (d != n / d)
                nr++;          // divizorul n/d
        }
    return nr;
}

Subprogramul nrDiv(n)

• nr pornește de la 0
• pentru d de la 1, cât timp d·d ≤ n
  • dacă d îl divide pe n
    • se numără divizorul d
    • dacă n/d este diferit de d, se numără și divizorul n/d
• se returnează nr

Pentru n = 27 se găsesc 1 cu perechea 27 și 3 cu perechea 9, deci se returnează 4. Căutarea face cel mult 1000 de pași, deoarece 1000 · 1000 = 10⁶.

int main() {
    ifstream f("def2024.in");
    int k, x, y;
    f >> k >> x >> y;
    f.close();

    if (x > y) {               // capetele, in ordine
        int aux = x;
        x = y;
        y = aux;
    }

    int nr = 0;
    int dCurent = nrDiv(x);    // divizorii lui i
    for (int i = x; i < y; i++) {
        int dUrm = nrDiv(i + 1);   // divizorii lui i+1
        if (dCurent == k && dUrm == k)
            nr++;
        dCurent = dUrm;
    }

    cout << nr;
    return 0;
}

Programul principal

• se citesc din fișier k, x și y
• dacă x > y, valorile lui x și y se interschimbă, astfel încât intervalul să fie [x, y]
• dCurent primește numărul divizorilor lui x
• pentru i de la x la y − 1
  • dUrm primește numărul divizorilor lui i + 1
  • dacă dCurent și dUrm sunt egale cu k, i și i + 1 formează o k-pereche și se numără
  • dCurent primește dUrm: numărul i + 1 devine primul număr al perechii următoare
• se afișează numărul perechilor

Fiecare număr din interval trece o singură dată prin nrDiv.

#include <iostream>
#include <fstream>
using namespace std;

/* Returneaza n daca n este perfect, 0 altfel. */
int perfect(int n) {
    if (n < 2)
        return 0;
    int s = 1;                 // divizorul propriu 1
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            s = s + d;
            if (d != n / d)
                s = s + n / d;
        }
    if (s == n)
        return n;
    return 0;
}

Subprogramul perfect(n)

• 0 și 1 nu sunt perfecte: se returnează 0
• s pornește de la 1, deoarece 1 este divizor al oricărui n ≥ 2
• pentru d de la 2, cât timp d·d ≤ n
  • dacă d îl divide pe n
    • d se adună la s
    • dacă n/d este diferit de d, se adună și n/d
• dacă s este egal cu n, se returnează n; altfel se returnează 0

Căutarea începe de la 2, deci divizorul n, pereche a lui 1, nu se adună.

int v[301];

int main() {
    ifstream f("nr17.txt");
    int n, x, k = 0;
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> x;
        if (perfect(x) != 0) {
            k++;
            v[k] = x;
        }
    }
    f.close();

    if (k == 0) {
        cout << "NU EXISTA";
        return 0;
    }

    /* ordonare descrescatoare */
    for (int i = 1; i < k; i++)
        for (int j = i + 1; j <= k; j++)
            if (v[i] < v[j]) {
                int aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }

    for (int i = 1; i <= k; i++)
        cout << v[i] << " ";
    return 0;
}

Programul principal

• se citește n, numărul de valori din fișier
• pentru fiecare dintre cele n valori x
  • dacă perfect(x) este diferit de 0, k crește cu 1 și x se memorează în v[k]
• dacă k este 0, se afișează NU EXISTA și programul se încheie
• vectorul se ordonează descrescător
  • pentru fiecare poziție i, se compară v[i] cu fiecare element de după el
  • dacă un element de după el este mai mare, cele două se interschimbă
• se afișează elementele vectorului

#include <iostream>
using namespace std;

/* Afiseaza factorii primi ai lui n, cu puterile lor. */
void descompunere(int n) {
    int primul = 1;    // 1 cat timp nu s-a afisat nimic
    for (int d = 2; d * d <= n; d++) {
        int p = 0;
        while (n % d == 0) {
            n = n / d;
            p++;
        }
        if (p > 0) {
            if (primul == 0)
                cout << ", ";
            cout << d << "^" << p;
            primul = 0;
        }
    }
    if (n > 1) {       // a ramas un factor prim
        if (primul == 0)
            cout << ", ";
        cout << n << "^1";
    }
}

Subprogramul descompunere(n)

• primul are valoarea 1 cât timp nu s-a afișat niciun factor
• pentru d de la 2, cât timp d·d ≤ n
  • p, puterea lui d, pornește de la 0
  • cât timp d îl divide pe n, n se împarte la d și p crește cu 1
  • dacă p > 0
    • dacă s-a afișat deja un factor, se afișează virgula și spațiul
    • se afișează d, semnul ^ și p
    • primul devine 0
• dacă n > 1, valoarea rămasă este un factor prim, la puterea 1
  • se afișează, precedată de virgulă dacă nu este primul factor

Un divizor d găsit astfel este prim: factorii primi mai mici decât el au fost deja eliminați din n.

int main() {
    int n;
    cin >> n;
    descompunere(n);
    return 0;
}

Programul principal

• se citește n
• se apelează subprogramul descompunere(n)