imagine-fundal

Blog / 🥇 Algoritmi de divizibilitate C++ (eficient și neficient)
facebook instagram whatsapp tiktok twitter

     În tutorialul de astăzi vom parcurge algortimi de prelucrare ai divizorilor unui număr citit de la tastatură. Există tot felul de probleme în care regăsim divizibilitatea și după cum veți afla de-a lungul articolului, putem modifica programele pentru a rezolva alt tip de probleme, de exemplu verificarea de număr prim, metoda eficient găsind-o pe ancora de aici. Înainte de a începe trebuie menționat că toți algoritmii prezentați funcționează în orice limbaj de programare, însă pentru popularitatea și comoditatea oferită îi vom scrie acum în C++ Imagine C++. Acum trebuie să înțelegem ce înseamnă un divizorul unui număr. Numim divizorul lui 12 numărul 6, deoarece 12 % 6 = 0. Mulțimea divizorilor se poate calcula totodată folosind indicatorul lui euler, algoritm pe care îl poți parcurge pe site. Tehnicile folosite sunt aproximativ aceleași, așa că explicațiile sunt la modul general. Mai jos puteți vedea implementările în limbaj pentru cerința: Să se determine suma divizorilor unui număr citit de la tastatură.

     Citim într-o variabilă numărul ai cărui divizori vrem să îi prelucrăm. Acum, în funcția divizori(), de tip void, pentru a modifica datele prezente de-a lungul întregului program, având un singur parametru de intrare, numărul salvat anterior, vom executa prelucrarea.

Varianta 1 - neficientă, vom parcurge toate numerele de la 1 la n, verificând dacă sunt divizori, în cazul favorabil îi putem prelucra, de exemplu îi vom adăuga la suma pentru a calcula totalul divizorilor.

#include <iostream>
using namespace std;
int S = 0;
void divizori(int n) {
    for (int d = 1; d <= n; d++) 
        if (n % d == 0)
            S = S + d; // prelucrare divizor d
}
int main() {
    int n;
    cin >> n;
    divizori(n);
    cout << S;
    return 0;
}

Varianta 2 - eficientă, vom parcurge toate numerele de la 1 la sqrt(n), verificând dacă sunt divizori câte 2 odată, divizorul d și cel n / d. Aceasta este variantă corectă, acceptată în probleme pentru a obține punctaj maxim.

#include <iostream>
using namespace std;
int S = 0;
void divizori(int n) {
    for (int d = 1; d * d <= n; d++) 
        if (n % d == 0) {
            S = S + d; // prelucrare divizor d
            if (d * d < n) 
                S = S + n / d; // prelucrare divizor n / d
        }
}
int main() {
    int n;
    cin >> n;
    divizori(n);
    cout << S;
    return 0;
}

     Acum că am văzut implementările, putem verifica cu ajutorul acestora dacă un număr este prim, deoarece cunoaștem faptul că un număr prim are doar doi divizori, pe unu și pe el însuși. Pentru aceasta vom contoriza într-o variabilă numărul divizorilor, apoi, dacă este egal cu 0 considerăm prim numărul testat.

#include <iostream>
using namespace std;
int nrdiv = 0;
void divizori(int n) {
    for (int d = 1; d * d <= n; d++) 
        if (n % d == 0) {
            nrdiv++;
            if (d * d < n) 
                nrdiv++;
        }
}
int main() {
    int n;
    cin >> n;
    divizori(n);
    if (nrdiv == 2) 
        cout << "nr prim";
    else 
        cout << "nu e prim";
    return 0;
}

Înainte de a încheia articolul recomandăm spre rezolvare următoarele probleme de pe platforma PBinfo: numarul-de-divizori, suma-divizorilor, numarul-divizorilor-pari

imagine

pbinfo / 1452

imagine

cssbattle / 6

imagine

pbinfo / 3074